Domain 2MediumCORE

Subarray Sum Equals K

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Hash Table

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:

  1. 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.
  2. 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.
  3. 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 O(N2)O(N^2) time complexity. Given nums.length can be up to 20,000, an N2N^2 approach is too slow (4×1084 \times 10^8 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: P[i]−P[j]=k  ⟹  P[j]=P[i]−kP[i] - P[j] = k \implies P[j] = P[i] - 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 O(N)O(N) time complexity.

Approach

  1. Initialize count = 0 and current_sum = 0.
  2. Create a hash map (prefix_counts) to store frequencies of prefix sums encountered so far.
  3. 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).
  4. 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 to count because those instances represent valid subarrays ending at the current index.
    • Update the map with the new current_sum, incrementing its count (or initializing it).
  5. Return count.

Complexity Analysis

  • Time: O(N)O(N), where N is the length of nums. We traverse the array exactly once, and hash map operations are average O(1)O(1).
  • Space: O(N)O(N) 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 equals k immediately (e.g., [5], k=5), it is counted correctly.
  • Negative Numbers in Array: Since we use a hash map rather than a sliding