#560

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Subarray Sum Equals K

Count the total number of contiguous subarrays in an integer array that sum exactly to a target value k using optimized scanning.

array hash table prefix sum

Problem Statement

Given an integer array nums and an integer k, determine the total number of contiguous subarrays whose sum equals k. Each subarray must consist of consecutive elements in nums.

For example, with nums = [1,1,1] and k = 2, there are 2 subarrays that meet the criteria. Implement an efficient solution that handles large arrays without checking all possible subarrays explicitly.

Examples

Example 1

Input: nums = [1,1,1], k = 2

Output: 2

Example details omitted.

Example 2

Input: nums = [1,2,3], k = 3

Output: 2

Example details omitted.

Constraints

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

Solution Approach

Prefix Sum with Hash Map

Maintain a running prefix sum and use a hash map to store how many times each sum has occurred. For each element, increment the count by the number of times (currentSum - k) appears in the map. This exploits the array scanning plus hash lookup pattern and avoids nested iteration.

Iterative Single Pass

Scan through nums once, updating the current cumulative sum and consulting the hash map in each iteration. Add currentSum to the map after counting. This ensures O(n) time and captures all valid subarrays without recomputation.

Edge Case Handling

Initialize the hash map with {0:1} to account for subarrays starting at index 0. Carefully handle negative numbers and zeros, as they may influence the prefix sums and hash lookups, ensuring correctness across all integer ranges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each element is processed once and hash map lookups are constant on average. Space complexity is O(n) due to storing prefix sums in the hash map.

What Interviewers Usually Probe

Checks if candidate considers brute-force inefficiency with nested loops.
Looks for use of prefix sum combined with hash lookup to count subarrays.
Observes whether edge cases like negative numbers and zero sums are handled correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize hash map with 0:1, causing missed subarrays starting at index 0.
Using nested loops which lead to O(n^2) performance and timeouts.
Neglecting negative numbers or zeros which can invalidate prefix sum assumptions.

Follow-up variants

Return all subarrays themselves instead of just the count using a similar prefix sum map.
Find the longest subarray with sum equal to k, adjusting the map to store earliest indices.
Count subarrays with sum less than or equal to k, modifying lookup logic to handle ranges.

FAQ

What is the most efficient approach for Subarray Sum Equals K?

Use a prefix sum combined with a hash map to count occurrences of currentSum - k, achieving O(n) time complexity.

Can negative numbers be handled in this problem?

Yes, the prefix sum plus hash map approach works with negative numbers because it tracks cumulative sums accurately.

Why not use a brute-force nested loop?

Nested loops lead to O(n^2) time and will fail on large arrays; prefix sum with hash lookup is necessary for efficiency.

How do I account for subarrays starting at index 0?

Initialize the hash map with {0:1} to count subarrays that sum to k from the beginning of the array.

What pattern does this problem exemplify?

It exemplifies the array scanning plus hash lookup pattern where cumulative sums are mapped to frequencies for quick subarray counting.

terminal

Solution

Solution 1: Hash Table + Prefix Sum

We define a hash table `cnt` to store the number of times the prefix sum of the array `nums` appears. Initially, we set the value of `cnt[0]` to `1`, indicating that the prefix sum `0` appears once.

1

2

3

4

5

6

7

8

9

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = Counter({0: 1})
        ans = s = 0
        for x in nums:
            s += x
            ans += cnt[s - k]
            cnt[s] += 1
        return ans

Continue Practicing

#525 contiguous array #523 continuous subarray sum #930 binary subarrays with sum