Subarray Sum Equals K

Tips

题目类型: 前缀和 + HashMap

Problem

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Examples

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: [1,1] and [1,1] are two different subarrays.

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: The subarrays are [1,2] and [3].

Solution

Prefix Sum + HashMap (Optimal)

Key Insight:

Let pre[i] be the sum of elements from index 0 to i, then pre[i] = pre[i-1] + nums[i]
The condition "subarray pre[j..i] has sum k" can be transformed to: pre[i] = pre[j-1] + k
Rearranging: pre[j-1] = pre[i] - k

We can use a HashMap to store prefix sums as keys and their frequencies as values. For each position i, we check if pre[i] - k exists in the map, which means there's a subarray ending at i with sum k.

Algorithm:

Initialize a HashMap with {0: 1} (base case: empty prefix has sum 0)
Iterate through the array:
- Calculate running prefix sum
- If (preSum - k) exists in the map, add its frequency to count
- Update the frequency of current prefix sum in the map
Return the total count

Time Complexity: O(n) - single pass through the array Space Complexity: O(n) - HashMap storage

function subarraySum(nums: number[], k: number): number {
  // Initialize map with 0: 1 (empty prefix)
  const map = new Map([[0, 1]])

  let preSum = 0
  let count = 0

  for (const num of nums) {
    preSum += num
    // Check if there exists a prefix with sum (preSum - k)
    if (map.has(preSum - k)) {
      count += map.get(preSum - k)
    }

    // Update frequency of current prefix sum
    map.set(preSum, (map.get(preSum) || 0) + 1)
  }

  return count
}

Example walkthrough:

For nums = [1, 1, 1], k = 2:

Initial: map = {0: 1}, preSum = 0, count = 0

i=0, num=1:
  preSum = 1
  Check preSum - k = 1 - 2 = -1, not in map
  map = {0: 1, 1: 1}

i=1, num=1:
  preSum = 2
  Check preSum - k = 2 - 2 = 0, exists! count += 1
  map = {0: 1, 1: 1, 2: 1}

i=2, num=1:
  preSum = 3
  Check preSum - k = 3 - 2 = 1, exists! count += 1
  map = {0: 1, 1: 1, 2: 1, 3: 1}

Result: count = 2

Problem​

Solution​

Problem

Solution