The O(n) Club: Subarray Sum Equals K

The O(n) Club: Subarray Sum Equals K – But Make It Fashion

⚡ TL;DR

Given an array and target k, count the number of CONTIGUOUS subarrays that sum to exactly k. Brute force might be your emotional support duck, but it drowns in O(n²):

🧠 How Devs Usually Mess This Up

No shame—most of us try double for-loops first, thinking “Big-O can’t be THAT bad, right?” But when your LeetCode input is ‘thicc’, two nested loops will make your code sweat so hard it gets TLE’d out of the room. Bonus: People often mix up subarrays (contiguous) with subsequences (chaotic free-for-all picks). Don’t be that person.

🔍 What’s Actually Going On

The real magic: walk through the array with a running sum (prefix sum), but instead of living in the past, you use a HashMap to “remember” every sum you’ve ever hit. Whenever your running sum minus k shows up in this map, it means you’ve found a streak of numbers that sums to k. Like asking, “Did I have just enough snacks left then to eat exactly k by now?” Immediate results, no rewind button required.

🛠️ PseudoCode

Remember the current sum for later:

map.put(sum, map.getOrDefault(sum, 0) + 1);

For each step, if sum - k exists in the map, add its value to the answer — because you just hit another subarray-ending jackpot.

if (map.containsKey(sum - k)) {
    count += map.get(sum - k);
}

Walk through the array, adding each number to the sum:

int sum = 0;
for (int num : nums) {
    sum += num;
    // (rest of the algorithm...)
}

Start with a HashMap storing cumulative prefix sums and their counts:

Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // Just in case you hit k right from the start

💻 The Code

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        count += map.getOrDefault(sum - k, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

No-commit subarrays: Only contiguous elements count, not sequenced pick-and-mix.
Negatives/Zeroes: Don’t sweat it — prefix sums + HashMap laughs at negative numbers and zeroes alike.
Forgot to map.put(0,1): You’ll miss subarrays starting at 0 — and your count will be sad.
Time/Space: O(n) for both. If n is gigantic and most prefix sums are unique (rare), the map gets chunky but stays cool under pressure.