0560.Subarray Sum Equals K

Link: 560. Subarray Sum Equals K - Medium
Track: Amazon Tag

Question

Restate the problem

• Given an array of integers nums
• Return the total number of subarrays, sum equal to k
  • range: -1000 <= nums[i] <= 1000
  • contiguous subarray

Edge Case

• Empty array: nums = [] → answer is 0
• Subarray starts at index 0: nums = [3], k = 3
  • Needs dic = {0:1} so total==k is counted.
• nums=[1,-1,0], k = 0 → return 3

---

Method 1 - Prefix
Method 2

Method 1 - Prefix

Key insight:

• prefix[j] - prefix[i] = k
• means the contiguous subarray nums[i+1..j] sums to k

Approach

• Initialize dic = {0: 1}
  • to represent the empty prefix (sum 0) occurring once, so subarrays that start at index 0 can be counted when total == k.
• Use a running prefix sum total.
• For each number:
  • total += num
  • Add dic.get(total - k, 0) to count (number of previous prefixes that make a subarray sum to k)
  • Update frequency: dic[total] = dic.get(total, 0) + 1

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Code

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = {0: 1} # dic = {total: freq}
        total = 0
        count = 0
        for idx, num in enumerate(nums):
            total += num 
            diff = total - k
            if diff in dic:
                count += dic[diff]
            
            dic[total] = dic.get(total, 0) + 1
        
        return count

Sample

sample:
[1, 1, 1]
1, total: 1 - k = -1, dic{0:1, 1:1}
1, total: 2 - k = 0,  dic{0:1, 1:1, 2:1} -> count = 1 
1, total: 3 - k = 1,  dic{0:1, 1:1, 2:1, 3:1} -> count = 2

---

History

• Feb-15-2026 Hinted
  • dic[total] = dic.get(total, 0) + 1
• Feb-11-2026 Peeked
  • use wrong algorithm