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.
function subarraySum(nums, k) {
let count = 0,
sum = 0,
map = new Map();
map.set(0, 1);
for (let num of nums) {
sum += num;
if (map.has(sum - k)) count += map.get(sum - k);
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
Follow-up:
What if the array is very large and we need to find the subarray sum in real-time?
