Skip to main content

19. Subarray Sum Equals K

mediumAsked at Baidu

Count the number of contiguous subarrays whose elements sum exactly to k.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k. Note negatives are allowed, so sliding window is not directly applicable.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Two nested loops

For every start index, sweep forward summing until either k is hit or end.

Time
O(n^2)
Space
O(1)
let c=0;for(let i=0;i<nums.length;i++){let s=0;for(let j=i;j<nums.length;j++){s+=nums[j];if(s===k)c++;}}return c;

Tradeoff:

2. Prefix sum + hash map

Track running prefix sum and a frequency map of past prefixes; for each i add freq[prefix-k].

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const counts = new Map();
  counts.set(0, 1);
  let prefix = 0, result = 0;
  for (const x of nums) {
    prefix += x;
    result += counts.get(prefix - k) || 0;
    counts.set(prefix, (counts.get(prefix) || 0) + 1);
  }
  return result;
}

Tradeoff:

Baidu-specific tips

Baidu loves the prefix-sum-map trick because the same shape powers their inverted-index range-count queries, so they will probe whether you know why sliding window fails on negatives.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Subarray Sum Equals K and other Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →