IntermediateArraysHashing
Subarray Sum Equals K
Problem
Given an array of integers nums (which may include negatives and zeros) and an integer k, return the total number of contiguous subarrays whose sum equals exactly k. Subarrays are counted by position, so identical values at different positions count separately.
Constraints
- 1 ≤ n ≤ 2·10^4
- -1000 ≤ nums[i] ≤ 1000
- -10^7 ≤ k ≤ 10^7
Examples
in: nums = [1,1,1], k = 2
out: 2
[1,1] at positions 0–1 and 1–2.
in: nums = [1,2,3], k = 3
out: 2
[1,2] and [3].
What this tests
- Prefix sums as a way to express subarray sums as differences
- Recognising why sliding window fails with negative numbers
- Counting with a hash map of prefix-sum frequencies
- The
prefix[0] = 0seed and why it is necessary - Handling repeated prefix values
Pattern RecognitionOptimizationSystematic ReasoningEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
All numbers are positive. Can you reduce the space?
F2
Count subarrays whose sum is divisible by
k.F3
Find the *longest* subarray with sum
k instead of counting.F4
The input is a 2-D matrix and you need the number of submatrices summing to
k.