#560 Subarray Sum Equals K
frequently reported atMetaInfosysMicrosoftAmazonBloombergByteDance / TikTok
the problem
In plain words
Return the number of contiguous, non-empty subarrays whose elements add up to exactly k. Values can be negative.
in nums = [1,1,1], k = 2
out 2
in nums = [1,2,3], k = 3
out 2
[1,2] and [3].
- 1 ≤ n ≤ 2·10⁴
- -1000 ≤ nums[i] ≤ 1000
- -10⁷ ≤ k ≤ 10⁷
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix sum + HashMap
sum(j..i) = P[i+1] − P[j]. So at each position, the number of good subarrays ending here = how many earlier prefix sums equal current − k.
solutions
From brute force to optimal
Three loops: start, end, and a loop that adds the range.
- For each start, each end ≥ start, add nums[start..end] and compare with k.
O(n²) subarrays × O(n) to sum each.
A counter.
class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { for (int end = start; end < nums.length; end++) { int sum = 0; for (int i = start; i <= end; i++) sum += nums[i]; // re-add the whole range if (sum == k) count++; } } return count; }}Extending a subarray by one element just adds that element.
- For each start: sum = 0.
- For each end: sum += nums[end]; if sum == k, count++.
Every (start, end) pair, O(1) each.
A running sum.
class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; // extend the range by one: O(1) if (sum == k) count++; } } return count; }}Keep the running prefix sum and a map prefix → how many times seen. Look up sum − k before recording sum.
- seen = {0: 1}, sum = 0.
- For each x: sum += x.
- count += seen.getOrDefault(sum − k, 0).
- seen.merge(sum, 1, Integer::sum).
One pass with O(1)-average map work per element.
Up to n + 1 distinct prefix sums.
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> seen = new HashMap<>(); // prefix sum → how many times seen.put(0, 1); // the empty prefix, so subarrays starting at index 0 count int sum = 0, count = 0; for (int x : nums) { sum += x; count += seen.getOrDefault(sum - k, 0); // earlier prefixes that leave exactly k seen.merge(sum, 1, Integer::sum); } return count; }}Dry run
in the room
How to say it in the interview
talk track
- Say why sliding window fails: negatives mean growing the window can lower the sum.
- Write
sum(j..i) = P[i+1] − P[j] = k ⇒ P[j] = P[i+1] − kand the map follows. - Call out the
{0: 1}seed and the order: look up, then store (the empty subarray must not count).
traps
- Missing
seen.put(0, 1): subarrays starting at index 0 aren't counted. - Storing a boolean or the first index instead of a count: several earlier prefixes can match.
what they ask next
Follow-ups
Return the longest such subarray instead (LC 325)?
Map prefix → first index. At each i, length = i − firstIndex[sum − k].
All numbers are positive?
Then sliding window works with O(1) space, because the sum grows monotonically with the window.
before you submit
Edge cases to test
- k = 0 with zeros ([0,0,0] → 6).
- Negative numbers ([1,-1,0], k = 0 → 3).
- A subarray starting at index 0 needs the {0: 1} seed.
practise next
Similar problems
- #974Subarray Sums Divisible by KMediumin Hashing
- #525Contiguous ArrayMediumin Hashing
- #1Two SumEasyin Hashing