Subarray Sum Equals K

medium prefix sum hash map

Problem

Count the number of contiguous subarrays whose elements sum to a given target k. Values may be negative.

Inputnums = [1, 1, 1], k = 2

Output2

If running prefix is P, count occurrences of P − k seen so far.

nums (comma-separated)

def subarray_sum(nums, k):
    counts = {0: 1}
    prefix = 0
    answer = 0
    for x in nums:
        prefix += x
        answer += counts.get(prefix - k, 0)
        counts[prefix] = counts.get(prefix, 0) + 1
    return answer

function subarraySum(nums, k) {
  const counts = new Map([[0, 1]]);
  let prefix = 0, answer = 0;
  for (const x of nums) {
    prefix += x;
    answer += counts.get(prefix - k) || 0;
    counts.set(prefix, (counts.get(prefix) || 0) + 1);
  }
  return answer;
}

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

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> counts;
    counts[0] = 1;
    int prefix = 0, answer = 0;
    for (int x : nums) {
        prefix += x;
        if (counts.count(prefix - k)) answer += counts[prefix - k];
        counts[prefix]++;
    }
    return answer;
}

Time: O(n) Space: O(n)