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.
def subarraySum(nums, k):
count, sum, map = 0, 0, {0:
1} for num in nums:
sum += num if sum - k in map:
count += map[sum - k] map[sum] = map.get(sum, 0) + 1 return countFollow-up:
What if the array is very large and we need to find the subarray sum in real-time?
