Back to solutions

Subarray Sum Equals K

MediumArrays

Count contiguous subarrays whose sum equals k.

Open problem
Constraints
  • 1 <= n <= 2*10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Prefix sum counts

Time O(n)Space O(n)

A subarray sums to k when prefix[j] - prefix[i] = k, i.e. prefix[i] = prefix[j] - k. Sweep once keeping a running prefix sum and a map of how many times each prefix value has occurred. For each new prefix, add the number of earlier prefixes equal to sum - k.

Key terms
prefix sum:
The running total of the array from the start to the current index.
complement prefix:
The earlier prefix value (sum - k) that would make the in-between subarray sum to k.
int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> cnt; cnt[0] = 1;
    long long sum = 0; int res = 0;
    for (int x : nums) {
        sum += x;
        res += cnt.count(sum - k) ? cnt[sum - k] : 0;
        cnt[sum]++;
    }
    return res;
}
Step by step
  1. Initialise a map with prefix 0 seen once (an empty prefix).
  2. Keep a running sum; for each element add it to sum.
  3. Add to the answer the count of prefixes equal to sum - k seen so far.
  4. Record the current sum in the map and continue.