Subarray Sum Equals K

MediumArray Hash Table Prefix Sum

A food truck records its net result for each day in nums: a loss is negative and a day with no sales is 0. The owner wants to know in how many periods of consecutive days the truck earned exactly k in total.

Count the non-empty contiguous subarrays of nums whose sum equals k. Two periods that start or end on different days are counted separately, even when they overlap.

Example 1

Input: nums = [4,-1,1,4], k = 4
Output: 4

Explanation: The periods are [4] on day 0, [4,-1,1], [-1,1,4] and [4] on day 3.

Example 2

Input: nums = [5,-5,5], k = 5
Output: 3

Explanation: Day 0 alone, day 2 alone, and all three days together.

Example 3

Input: nums = [2,6,-1,-4], k = 10
Output: 0

Explanation: No period adds up to 10.

Constraints

nums has between 1 and 20,000 entries.
Each daily result is an integer from -1000 to 1000.
k is between -10^7 and 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