Subarray Sum Equals K — DSA

Problem

Given an integer array nums and an integer k, return the number of contiguous subarrays whose elements sum to exactly k.

Input:  nums = [1, 1, 1], k = 2      →   2     ([1,1] at positions 0–1 and 1–2)
Input:  nums = [1, 2, 3], k = 3      →   2     ([1,2] and [3])
Input:  nums = [1, -1, 0], k = 0     →   3     ([1,-1], [0], [1,-1,0])

nums can contain negative numbers and zeros. That's why the sliding-window technique doesn't work here: extending a window doesn't reliably increase its sum.
Count every qualifying subarray, including overlapping ones.
The intended O(n) solution combines prefix sums with a hash map of how many times each prefix sum has occurred.

Examples

Example 1

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

Output: 2

Explanation: Two subarrays sum to 2: [1,1] (indices 0-1) and [1,1] (indices 1-2).

Example 2

Input: nums = [1,2,3], k = 3

Output: 2

Explanation: [1,2] and [3] both sum to 3.

Constraints

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

Hints

Hint 1

The brute force checks every subarray's sum directly — O(n^2). What running value, tracked as you scan once, could avoid recomputing each subarray's sum from scratch?

Hint 2

If prefixSum[j] - prefixSum[i] == k, the subarray between i+1 and j sums to k. Rearranged: prefixSum[i] == prefixSum[j] - k.

Hint 3

A hash map from 'prefix sum value seen so far' to 'how many times' turns the search for prefixSum[i] into an O(1) lookup instead of an O(n) scan.

Solutions

public int subarraySumBruteForce(int[] nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

Time: O(n^2) · Space: O(1)