Skip to main content

20. Subarray Sum Equals K

mediumAsked at LINE

Count contiguous subarrays whose sum equals k — LINE uses this to test prefix-sum + hash-map reflexes, the engine behind their transaction-rollup audit jobs.

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

Problem

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

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. Brute force pairs

Sum every (i, j) range explicitly and count matches.

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

Tradeoff:

2. Prefix sum with hash map

Keep a running prefix sum. At each step, the count of subarrays ending here that sum to k equals the number of prior prefixes equal to prefix - k. Track frequencies in a map.

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

Tradeoff:

LINE-specific tips

At LINE, frame the prefix-sum map as how you'd count LINE Pay subwindows whose net flow equals a refund target — payment-integration framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →