20. Subarray Sum Equals K

MediumArray Hash Table Prefix Sum

Given an integer array nums and an integer k, return how many non-empty contiguous subarrays of nums have a sum equal to k.

The array may contain negative numbers and zeros, so subarrays that start at different positions but overlap each count separately.

Example 1

Input: nums = [2,2,2], k = 4
Output: 2

Explanation: Indices 0..1 and 1..2 both sum to 4.

Example 2

Input: nums = [3,4,7,-2,2,1,4,2], k = 7
Output: 6

Explanation: The subarrays are [3,4], [7], [7,-2,2], [2,1,4], [-2,2,1,4,2] and [1,4,2].

Example 3

Input: nums = [1,-1,0], k = 0
Output: 3

Explanation: [1,-1], [0] and [1,-1,0].

Constraints

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

💡 Hint 1

Negative numbers break the usual sliding-window trick: growing a window does not always increase its sum.

💡 Hint 2

Let prefix[j] be the sum of the first j elements. The subarray from i to j - 1 sums to k exactly when prefix[j] - prefix[i] == k.

💡 Hint 3

Scan once, keeping a hash map from each prefix sum to how many times it has occurred. At each step, add the number of earlier prefixes equal to current - k.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use prefix sums with a hash map. While scanning, keep the running sum sum of the elements so far and a map seen from each earlier prefix sum to how many times it occurred, starting with {0: 1} for the empty prefix. A subarray ending at the current element sums to k exactly when some earlier prefix equals sum - k, so add seen[sum - k] to the answer, then record sum in the map. This counts every subarray once, in a single pass.

Time O(n)Space O(n)

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);
  let sum = 0;
  let count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) ?? 0;
    seen.set(sum, (seen.get(sum) ?? 0) + 1);
  }
  return count;
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int sum = 0, count = 0;
        for (int x : nums) {
            sum += x;
            count += seen.getOrDefault(sum - k, 0);
            seen.merge(sum, 1, Integer::sum);
        }
        return count;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function subarraySum(nums, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit