Subarray Sum Equals K Problem
Description
LeetCode Problem 560. Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
Example:
1
2
Input: nums = [1, 2, 3], k = 3
Output: 2
Solution
This problem is similar to the two sum problem.
Brute Force Approach
A simple solution is to use the brute force approach. We can consider all possible subarrays and check the sum of each subarrays with the given integer k.
We can use a left pointer l and a right pointer r to enumerate all possible subarrays. We loop through each integer in the array nums with l. For each l, we iterate with r from l+1 to the end of the array. In the meantime, we use a sum variable to record the accumulative sum from l to r. If sum equals k, we can increase the total count; otherwise, we can keep on searching.
The time complexity of this approach is O(n2), and the space complexity is O(1).
Hash Table Approach
The time complexity can be further reduced if we use a hash table to store intermediate results (similar to the two sum problem).
We loop through the array and use an accu_sum variable to store the accumulative sum. For each distinctive accu_sum, we use a hash table to store how many times this accu_sum has occurred.
During the iteration, if the current accu_sum is greater than k, and (accu_sum-k) exists in the hash table, it means the sum of integers in the array between (accu_sum-k) and accu_sum is k. So we have found solutions. The number of possible subarrays depends on how many (accu_sum-k) are there (stored as the value in the hash table). We can increase the total count with this value.
After we finish the iteration, we can find the number of all possible subarrays.
One thing to note is that before we start the iteration, we store the key-value pair (0, 1) to the hash table. In that case, if the accumulative sum is k, we will have 1 answer at least (unless there are other subarrays with accu_sum to be 0).
Here is a complete walk through of the hash table approach. The array nums is {1, 2, 2, 1, 3}, and k is 3.
1
2
3
4
5
6
7
8
9
10
| nums | accu_sum | count | ht (accu_sum, cnt)
| 1 | 2 | 2 | 1 | 3 | - | - | (0,1)
i | 1 | 0 | (0,1) (1,1) <-- accu_sum < k
i | 3 | 1 | (0,1) (1,1) (3,1) <-- ht[accu_sum-k] = ht[0] = 1 => count = 1
i | 5 | 1 | (0,1) (1,1) (3,1) <-- ht[accu_sum-k] = ht[2] doesn't exist => count = 1
| | | (5,1)
i | 6 | 2 | (0,1) (1,1) (3,1) <-- ht[accu_sum-k] = ht[3] = 1 => count = 2
| | | (5,1) (6,1)
i | 9 | 3 | (0,1) (1,1) (3,1) <-- ht[accu_sum-k] = ht[6] = 1 => count = 3
| | | (5,1) (6,1) (9,1)
The time complexity can be reduced to O(n), while the space complexity is still O(n).
Sample C++ Code
This is a C++ implementation of the hash table approach.
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
unordered_map<int, int> ht;
int accu_sum = 0;
int count = 0;
ht[0] = 1;
for (int i = 0; i < len; i ++) {
accu_sum += nums[i];
if (ht.find(accu_sum) == ht.end())
ht[accu_sum] = 0;
if (ht.find(accu_sum-k) != ht.end()) {
count += ht[accu_sum-k];
}
ht[accu_sum] += 1;
}
return count;
}
int main() {
vector<int> nums={1,2,2,1,3};
int k = 3;
cout << subarraySum(nums, k) << endl;
}