Problem description:

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:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution:

The key of solving this problem is to find SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap.

example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
[2,3,2,5,8]
5

init state:
0, 1

round 1:
cur_sum: 2, ans: 0, cur-k: -3, count: 0 after_count: 0
 2, 1
 -3, 0
 0, 1

round 2:
cur_sum: 5, ans: 1, cur-k: 0, count: 1 after_count: 1
 2, 1
 -3, 0
 5, 1
 0, 1

round 3:
cur_sum: 7, ans: 2, cur-k: 2, count: 1 after_count: 1
 7, 1
 0, 1
 5, 1
 -3, 0
 2, 1

round 4:
cur_sum: 12, ans: 3, cur-k: 7, count: 1 after_count: 1
 12, 1
 7, 1
 0, 1
 5, 1
 -3, 0
 2, 1

round 5:
cur_sum: 20, ans: 3, cur-k: 15, count: 0 after_count: 0
 20, 1
 15, 0
 12, 1
 7, 1
 0, 1
 5, 1
 -3, 0
 2, 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # idea is to store appreaed values in hashmap
        # sum(0, y) - sum(0, x) = sum(x, y)
        res, cur, dic = 0, 0, defaultdict(int)
        dic[0] = 1
        for n in nums:
            cur += n
            if cur-k in dic:
                res += dic[cur-k]
            dic[cur] += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        unordered_map<int, int> counts{{0,1}};
        int cur_sum = 0;
        int ans = 0;
        
        for (auto num : nums) {
            cur_sum += num;
            ans += counts[cur_sum - k];
            ++counts[cur_sum];
        }
        return ans;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$

reference:
https://goo.gl/3nxf3P
https://goo.gl/T4kEoE