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.
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int num : nums) {
sum += num;
if (map.containsKey(sum - k)) count += map.get(sum - k);
map.put(sum, map.getOrDefault(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?
