⚡Flashcard Drill➔
NeetCode #111LC-560MediumArrays & HashingNC 250
← Back to All Problems

#111 · #560 · Subarray Sum Equals K(和为 K 的子数组)

📌 Problem Statement & Constraints

Given an array of integers nums and an integer k, return the total number of contiguous subarrays whose sum equals k. Constraints: 1 <= nums.length <= 2 * 10^4, -1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7.

💡 Core Algorithmic Approaches

  1. A sliding window fails because the array may contain negative numbers, so the running sum is not monotonic in the window bounds.
  2. Use prefix sums with a hash map. Let P[i] be the sum of the first i elements. Then sum(nums[i..j]) = P[j+1] - P[i].
  3. The condition P[j+1] - P[i] == k becomes P[i] == P[j+1] - k. So while scanning, count how many earlier prefix sums equal current - k.
  4. The map stores the frequency of each prefix sum, not just its presence, because multiple earlier prefixes may share the same value.
  5. Initialise the map with {0: 1} to represent the empty prefix, which handles subarrays starting at index 0.

💻 Benchmark Python3 Implementation

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        count = defaultdict(int)
        count[0] = 1                 # the empty prefix, sum 0, seen once
        prefix = 0
        res = 0
        for x in nums:
            prefix += x
            # any earlier prefix equal to (prefix - k) closes a valid subarray
            res += count[prefix - k]
            count[prefix] += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) average hash operations. The brute-force prefix-sum double loop is O(n^2).
💾 Space Complexity
O(n) for the hash map, which may hold up to n + 1 distinct prefix sums.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting count[0] = 1: subarrays that start at index 0 would be missed entirely.
  • Storing booleans instead of counts: two different start indices can share the same prefix sum, and each yields a distinct subarray.
  • Using a sliding window: it only works when all values are non-negative, which the constraints do not guarantee.
  • Incrementing the prefix count before adding to the result: an element would be allowed to pair with itself, counting empty subarrays when k == 0.
  • Assuming k must be positive: k can be negative, and the same algorithm handles it unchanged.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems