Optimizing Subarray Sums with Prefix Sum Logic

Nested loops are a total trap when you're trying to scale, and I learned that the hard way while tackling a LeetCode problem about finding continuous subarrays that sum to k. My initial instinct was to just hammer out a brute-force solution, but the second the test cases hit $10^5$ elements, my code just sat there spinning its wheels. It was a massive performance disaster.

The breakthrough comes when you stop trying to recalculate every possible range and start looking at the math of cumulative totals. There's this realization where you see that any subarray sum from l to r is really just prefix[r] - prefix[l-1]. If we're searching for a target k, we're basically solving for the moment when prefix[r] - k = prefix[l-1].

Instead of an $O(n^2)$ nightmare, you can actually achieve a smooth $O(n)$ linear pass by using a Hash Map to track the frequency of prefix sums as you go. Here is the logic that actually works:

function subarraySum(nums, k) {
 let map = new Map();
 map.set(0, 1); // crucial for subarrays starting at index 0
 let prefix = 0;
 let count = 0;
 for (const num of nums) {
  prefix += num; 
  const needed = prefix - k; 
  count += map.get(needed) || 0; 
  map.set(prefix, (map.get(prefix) || 0) + 1); 
 }
 return count;
}

I had to do some serious debugging to get the implementation perfect, so pay attention to these three things:

1. You absolutely must seed your map with map.set(0, 1). If you skip this, you're going to totally miss any subarrays that sum to k starting from the very first element.
2. The order of operations is everything. You have to check for the needed value before you update the map with the current prefix. If you swap them, you'll end up counting the current index as its own predecessor, which ruins the count.
3. Stick to a Map instead of a standard object. When you're dealing with negative numbers in prefix sums, Map is way more predictable for key handling.

Check how it behaves with these cases:

console.log(subarraySum([1,1,1], 2)); // Expected: 2
console.log(subarraySum([1,2,3], 3)); // Expected: 2
console.log(subarraySum([1,-1,0], 0)); // Expected: 4

This is the kind of pattern recognition that actually provides value to the user because the app doesn't hang when the input gets large. Once you grasp how to work with these cumulative properties, you're not just writing lines of code; you're building efficient systems.