Given an integer array nums and an integer k, count how many contiguous non-empty subarrays have a sum exactly equal to k. The array can contain negative numbers and zeros.
Example 1
Input: nums = [1,1,1], k = 2
Output: 2
The subarrays
[1,1] starting at index 0 and at index 1 both sum to 2.Example 2
Input: nums = [1,2,3], k = 3
Output: 2
[1,2] and [3].Constraints
- 1 <= nums.length <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
Hints
Frequently asked at: Meta, Google, Amazon, Goldman Sachs, Flipkart
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every start and end, O(n^2) with a running sum. Two pointers fail because negative numbers make window sums non-monotonic. Using prefix sums, a subarray ending at j has sum k exactly when some earlier prefix equals s - k, where s is the current prefix sum. So we keep a frequency map of prefix sums seen so far and add count[s - k] at each step.
Algorithm
- Create a map
countwith{0: 1}(the empty prefix). - Walk the array keeping a running sum
s. - Add
count[s - k](default 0) to the answer. - Increment
count[s]. - Return the answer.
Time:
O(n)Space: O(n)Interview tip: Forgetting to seed the map with
{0: 1} misses every subarray that starts at index 0. Also, add to the answer before inserting the current sum, or k = 0 counts empty subarrays.class Solution: def subarraySum(self, nums: List[int], k: int) -> int: count = defaultdict(int) # prefix sum -> how many times seen count[0] = 1 # empty prefix s = ans = 0 for x in nums: s += x ans += count[s - k] count[s] += 1 return ansCtrl + Enter runs the examples