560. Subarray Sum Equals K

• Difficulty: Medium

• Topics: Array, Hash Table

• Similar Questions:

  • Two Sum

  • Continuous Subarray Sum

  • Subarray Product Less Than K

  • Find Pivot Index

  • Subarray Sums Divisible by K

Problem:

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solutions:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ret = 0;
        int sum = 0;
        unordered_map<int, int> valueCount;
        ++valueCount[sum];

        for (auto num : nums) {
            sum += num;
            int target = sum - k;
            if (valueCount.count(target) > 0) {
                ret += valueCount[target];
            }
            ++valueCount[sum];
        }

        return ret;
    }
};