Count Windows Summing to K
MediumArrays & Hashing
Problem
A trader records the daily profit or loss of a strategy. She wants to know how many contiguous stretches of days produced a combined result of exactly k.
Given an integer array nums (values may be negative) and an integer k, return the number of non-empty contiguous subarrays whose sum equals k.
Example 1
- Input:
- nums = [1, 2, 1, 2, 1], k = 3
- Output:
- 4
[1, 2] twice and [2, 1] twice.
Example 2
- Input:
- nums = [3, -3, 3, -3], k = 0
- Output:
- 4
[3, -3] at positions 0–1 and 2–3, [-3, 3] at 1–2, and the whole array.
Constraints
- 1 ≤ nums.length ≤ 2·10^4
- -1000 ≤ nums[i] ≤ 1000
- -10^7 ≤ k ≤ 10^7
Hint
Show the first hint
Express the sum of nums[i..j] using prefix sums.
Walkthrough
How to approach it
01Clarify before coding
- Can values be negative? Yes, which rules out a sliding window (sums are not monotonic).
- Do overlapping subarrays count separately? Yes, every (start, end) pair is a distinct subarray.
- Is the empty subarray counted when k = 0? No, subarrays are non-empty.
02Brute force
For every start i, extend the end j and keep a running sum, counting each time it equals k.
Cost: O(n²) time, O(1) space: 2·10^8 additions for n = 2·10^4, borderline-to-too-slow and not what the interviewer wants.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.