Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: The subarrays [1,1] and [1,1] sum to 2.

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: The subarrays [1,2] and [3] sum to 3.

Example 3:

Input: nums = [1,-1,0], k = 0
Output: 3
Explanation: The subarrays [1,-1], [-1,0], and [1,-1,0] sum to 0.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Thinking Process

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0, sum = 0;
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        for(int num: nums) {
            sum += num;
            if(prefixSum.contains(sum - k)) {
                cnt += prefixSum[sum - k];
            }
            prefixSum[sum]++;
        }
        return cnt;
    }
};

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem

How the code works:

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input nums = [1,1,1], k = 2, expected output 2:

The subarrays [1,1] and [1,1] sum to 2.

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(n) - Hash map can store up to n distinct prefix sums

    Comparison with LC 325

Problem Goal Hash Map Value Key Difference
LC 325 Maximum length First occurrence index Tracks maximum length
LC 560 Count subarrays Count of occurrences Counts all subarrays

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
  2. Hash Map Counting: Count occurrences of each prefix sum to handle multiple subarrays with the same sum
  3. Initial State: Initialize with prefixSum[0] = 1 to handle subarrays starting from index 0
  4. Overlapping Subarrays: The algorithm correctly counts all overlapping subarrays that sum to k
  5. Zero Sum Handling: When k = 0, the algorithm correctly handles cases where prefix sums repeat

References

Template Reference