Subarray sum equals K.

Problem. Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum equals k. Values may be negative.

Brute force — O(n²) time

Fix each start index, extend the end, accumulate the running sum, and count hits:

int subarraySumBrute(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;
}

Correct, but quadratic. (And note: because values can be negative, a sliding window does not work — growing the window doesn't monotonically grow the sum, so you can't decide when to shrink.)

Optimal — prefix sums + a hash map of counts — O(n)

Let prefix[i] be the sum of nums[0..i]. A subarray (j, i] sums to k exactly when prefix[i] - prefix[j] == k, i.e. prefix[j] == prefix[i] - k. So as we scan and maintain the running prefix, each step asks: how many earlier prefixes equal prefix - k? That count is how many subarrays ending here sum to k. Store prefix→occurrence-count in a hash map.

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);            // empty prefix: handles subarrays starting at index 0
    int prefix = 0, count = 0;
    for (int n : nums) {
        prefix += n;
        count += prefixCount.getOrDefault(prefix - k, 0);   // earlier prefixes that close a k-sum here
        prefixCount.merge(prefix, 1, Integer::sum);          // record this prefix
    }
    return count;
}

Time: O(n), one pass. Space: O(n) for the prefix map.