Sweaty Imposter

Subarray Sum Equals K

MediumArrays & HashingNeetCode 150MidOpen on LeetCodeUpdated

You're given an integer array nums and an integer k. Return the number of contiguous, non-empty subarrays whose elements add up to exactly k. Subarrays are counted by position, so two different ranges holding the same values both count. The array can contain negative numbers and zeros, so extending a subarray can make its sum go down as well as up.

Examples

nums = [1,1,1], k = 2 returns 2

The subarrays at indices 0..1 and 1..2 each sum to 2. They hold the same values but sit at different positions, so both count.

nums = [1,2,3], k = 3 returns 2

[1,2] (indices 0..1) and [3] (index 2) both sum to 3.

nums = [1,-1,0], k = 0 returns 3

[1,-1], [0] and [1,-1,0] each sum to 0. The -1 is what lets a longer subarray come back down to the same total.

Constraints

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

Hints

Hint 1

The sum of nums[i..j] equals the total of the first j + 1 elements minus the total of the first i elements. Could you count matching pairs of running totals instead of pairs of endpoints?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Let prefix be the running total. A subarray ending at the current index sums to k exactly when some earlier prefix equals prefix - k, so the number of such subarrays is how many times prefix - k has appeared before. Keep a hash map of prefix-sum frequencies seeded with {0: 1} for the empty prefix, add the lookup to the answer, then record the current prefix. This handles negatives, which break a sliding window, in O(n) time and O(n) space.

Time

O(n)

Space

O(n)

Pitfall

Forgetting to seed the map with prefix sum 0 seen once, which silently misses every subarray that starts at index 0. Also look up prefix - k before recording the current prefix, or k = 0 will count the empty subarray.

Solutions

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