Subarray Sum Equals K

Problem Overview

Given an array of integers (which may include negative numbers) and a target k, count how many contiguous subarrays sum to exactly k.

Why solve this?

The problem that makes clear why a sliding window alone isn't a general subarray-sum tool: once negative numbers are allowed, growing and shrinking a window stops being a safe, monotonic operation, and a prefix-sum-plus-hashmap technique is needed instead.

Pattern Recognition

Whenever a problem counts subarrays matching a sum target and the array can contain negative numbers, translate it into 'how many earlier prefix sums equal (current prefix sum - k)' and track prefix-sum frequencies in a hash map while scanning once.

Prerequisites

• Contains Duplicate — the same hash-map-while-scanning shape, applied to prefix sums instead of raw values.

Hints

1. A subarray from index j+1 to i sums to k exactly when prefixSum[i] - prefixSum[j] = k — rearranged, prefixSum[j] = prefixSum[i] - k.
2. Instead of storing every prefix sum in an array, keep a running prefix sum and a hash map counting how many times each prefix-sum value has been seen so far.
3. Seed the map with 0 mapped to a count of 1 before scanning — this represents the empty prefix, needed so a subarray starting at index 0 can still be counted.

Approach

Maintain a running prefix sum as the array is scanned once, and a hash map from prefix-sum value to how many times it has occurred so far. At each element, add it to the running prefix sum, then look up prefixSum - k in the map: every earlier index where the prefix sum equalled that value marks the start of a subarray ending here that sums to exactly k, so add that count to the running total. Then record the current prefix sum in the map (incrementing its count). The map must be seeded with {0: 1} before the scan starts — this represents the 'empty prefix' before index 0, and without it a subarray that starts at index 0 and itself sums to k would never be counted, since there'd be no earlier occurrence of prefixSum - k = 0 on record.

Code

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

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy