560. Subarray Sum Equals K
Model: qwen3.5:9b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 43.7%
Problem Breakdown
We are given an array of integers nums and a target integer k. Our goal is to count how many continuous subarrays exist where their sum equals exactly k.
Key inputs: An array (nums) and a scalar value (k).
Output: A single integer representing the total count.
Constraints & Edge Cases:
- Negative Numbers: The input can contain negative integers (e.g.,
-2, -3), which immediately disqualifies standard sliding window approaches that rely on monotonicity. We must use a different technique. - Subarray starting at index 0: If the prefix sum itself equals
k, we need to count it. This implies our frequency map needs an initial state representing a “sum of zero” before any elements are processed. - Duplicates: Multiple subarrays might have the same values but different indices; each occurrence counts separately.
Intuition
A brute-force solution would iterate through every possible start and end index, calculating the sum for each window. This results in time complexity. Given nums.length can be up to 20,000, an approach is too slow ( operations).
The key insight relies on Prefix Sums.
Let P[i] be the sum of elements from index 0 to i. The sum of a subarray starting at j+1 and ending at i is P[i] - P[j].
We want this difference to equal k:
This transforms the problem: for every current prefix sum P[i], we need to know how many times a previous prefix sum of value (P[i] - k) has occurred. We can track these occurrences using a Hash Map (frequency map) as we iterate through the array once, achieving time complexity.
Approach
- Initialize
count = 0andcurrent_sum = 0. - Create a hash map (
prefix_counts) to store frequencies of prefix sums encountered so far. - Crucial Step: Before the loop, initialize
prefix_counts[0] = 1. This handles cases where the subarray starts from index 0 (where the required previous sum is effectively 0). - Iterate through each number in
nums:- Add current number to
current_sum. - Check if
(current_sum - k)exists in our map. If it does, add its frequency tocountbecause those instances represent valid subarrays ending at the current index. - Update the map with the new
current_sum, incrementing its count (or initializing it).
- Add current number to
- Return
count.
Complexity Analysis
- Time: , where N is the length of
nums. We traverse the array exactly once, and hash map operations are average . - Space: in the worst case (e.g., all prefix sums are distinct), to store the frequency map.
Solution
from typing import List
def subarraySum(nums: List[int], k: int) -> int:
# Map stores {prefix_sum : count}
# Initialize with 0 having a count of 1 to handle cases where
# the valid subarray starts from index 0.
prefix_counts = {0: 1}
current_sum = 0
total_count = 0
for num in nums:
current_sum += num
# We need a previous sum such that (current - prev) == k
# Therefore, we look for (current_sum - k)
target_prev_sum = current_sum - k
if target_prev_sum in prefix_counts:
total_count += prefix_counts[target_prev_sum]
# Update the frequency of the current running sum
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
return total_count
Edge Cases Handled
- Subarrays starting at index 0: The initialization
prefix_counts = {0: 1}ensures that if the running sum equalskimmediately (e.g.,[5], k=5), it is counted correctly. - Negative Numbers in Array: Since we use a hash map rather than a sliding