Subarray Sum Equals K
Given an array of integers `nums` and an integer `k`, return the total number of continuous subarrays whose sum equals `k`. A subarray is a contiguous part of an array.
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
Examples:
Input: nums = [1,1,1], k = 2
Output: 2
Explanation: There are two subarrays whose sum equals 2: [1,1] and [1,1].
Solutions
Hash Table
Time: O(n)Space: O(n)
We use a hash table to store the cumulative sum and its frequency. We iterate through the array, updating the cumulative sum and checking if the difference between the current sum and `k` exists in the hash table. If it does, we increment the count by the frequency of that difference.
int subarraySum(vector<int>& nums, int k) {
int count = 0, sum = 0;
unordered_map<int, int> map;
map[0] = 1;
for (int num : nums) {
sum += num;
if (map.find(sum - k) != map.end()) count += map[sum - k];
map[sum]++;
}
return count;
}Follow-up:
What if the array is very large and we need to find the subarray sum in real-time?
