1. Why the Sliding Window Technique Fails on Negative Numbers

Engineers often attempt to apply the two-pointer sliding window technique whenever a problem specifies "continuous subarrays." However, this approach relies on a critical mathematical invariant:

• Monotonicity Invariant: In an array containing strictly non-negative integers (arr[i] ≥ 0), expanding the right window pointer (right++) guarantees that the window sum will monotonically increase (or remain equal). Conversely, contracting the left pointer (left++) guarantees the sum will monotonically decrease. This predictability allows the two pointers to navigate the search space in linear time.
• The Negative Number Disruption: When an array contains negative integers (e.g., [10, 2, -2, -20, 10] with k = -10), expanding the window by including a negative number can decrease the cumulative sum, while contracting the window by dropping a negative number can increase it. Monotonicity is destroyed; knowing whether to advance the left or right pointer becomes impossible without exploring all combinatorial branches, causing the two-pointer technique to collapse.
• The O(n²) Brute-Force Fallback: Calculating all pairwise subarray sums via nested loops (i ∈ [0..n-1], j ∈ [i..n-1]) is computationally intractable for enterprise data sets, resulting in quadratic O(n²) execution latency that times out on large arrays.

2. The Prefix Sum + Hash Map State Machine

To achieve linear O(n) execution across arbitrary arrays with positive, negative, and zero values, we utilize a hash map to maintain a running frequency tally of historical prefix sums:

• Cumulative Sum Traversal: As we iterate sequentially through the array, we maintain a running accumulator: currentSum += arr[i].
• The Complement Lookup: At each index, we calculate the required complement: needed = currentSum - k. If needed exists in our frequency hash map with a count of C, it means there are exactly C distinct prior positions where the subarray ending at the current element equals k. We add C directly to our total match count.
• The Crucial Base Case map[0] = 1: If currentSum == k at any index, then currentSum - k = 0. To account for subarrays that originate from the very beginning of the array (index 0), the hash map must be pre-populated with {0: 1} before iteration begins. Omitting this base case results in off-by-one errors that fail tests.
• Map Update: Finally, we record the current prefix sum into the map: map[currentSum]++.

3. Production C++20 Implementation

Below is the complete C++20 implementation utilizing std::unordered_map and 64-bit integer accumulators to prevent numeric overflow:

#include <vector>
#include <unordered_map>
#include <cstdint>

class Solution {
public:
    int subarraySum(const std::vector<int>& nums, int k) {
        // Hash map storing: prefix_sum -> frequency count
        std::unordered_map<int64_t, int> prefixFreq;
        
        // Base case: prefix sum of 0 occurs once before array starts
        prefixFreq[0] = 1;

        int64_t currentSum = 0;
        int totalMatchCount = 0;

        for (int val : nums) {
            currentSum += val;
            
            // Invariant: If (currentSum - k) was seen before, those prior
            // cutoffs form continuous subarrays summing exactly to k.
            int64_t needed = currentSum - k;
            auto it = prefixFreq.find(needed);
            if (it != prefixFreq.end()) {
                totalMatchCount += it->second;
            }

            // Record current cumulative sum in the frequency register
            prefixFreq[currentSum]++;
        }

        return totalMatchCount;
    }
};

4. Production TypeScript Implementation

In TypeScript and Node.js environments, standard Map<number, number> provides deterministic O(1) key lookups with native IEEE-754 safe integer range support (up to Number.MAX_SAFE_INTEGER, ±9,007,199,254,740,991):

/**
 * Subarray Sum Equals K in TypeScript
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
export function subarraySum(nums: number[], k: number): number {
  // Map: prefixSum -> occurrence count
  const prefixMap = new Map<number, number>();
  
  // Seed base case: cumulative sum of 0 appears once before index 0
  prefixMap.set(0, 1);

  let currentSum = 0;
  let matchCount = 0;

  for (let i = 0; i < nums.length; i++) {
    currentSum += nums[i];

    const targetComplement = currentSum - k;
    const existingMatches = prefixMap.get(targetComplement);
    if (existingMatches !== undefined) {
      matchCount += existingMatches;
    }

    // Increment frequency tally
    const currentFrequency = prefixMap.get(currentSum) || 0;
    prefixMap.set(currentSum, currentFrequency + 1);
  }

  return matchCount;
}

5. Complexity Analysis & Architectural Takeaways

The time complexity is strictly O(n) because the algorithm processes each array element exactly once, performing constant-time O(1) hash table operations on average. The auxiliary space complexity is O(n) in the worst case (where all prefix sums are unique). This problem elegantly demonstrates the power of prefix transformations in computer science: by converting a range query problem into an arithmetic difference lookup, we eliminate redundant computation and reduce exponential combinatorial searches into linear execution pipelines.