52. Subarray Sum Equals K

🔗 LeetCode Problem: 560. Subarray Sum Equals K
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Prefix Sum

Problem Statement

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

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

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: There are 2 subarrays with sum = 2: [1,1] and [1,1]

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: There are 2 subarrays with sum = 3: [1,2] and [3]

Constraints: - 1 <= nums.length <= 2 × 10^4 - -1000 <= nums[i] <= 1000 - -10^7 <= k <= 10^7

🎨 Visual Understanding

The Problem Visualized

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

Check all subarrays:
[1] → sum = 1 ✗
[1, 2] → sum = 3 ✓ (count = 1)
[1, 2, 3] → sum = 6 ✗
[2] → sum = 2 ✗
[2, 3] → sum = 5 ✗
[3] → sum = 3 ✓ (count = 2)

Total count: 2

🚨 CRITICAL INSIGHT - Read This Carefully!

Question: "Can I just check if prefixSum equals k?"

Answer: NO! That only finds subarrays starting from index 0!

Example: nums = [1, 2, -1, 3], k = 2

Prefix sums:
Index:  -1   0   1   2   3
Prefix:  0   1   3   2   5

If we ONLY check prefixSum = 2:
  Found at index 2
  Count = 1

But there are MORE subarrays with sum = 2:
  [2] at index 1 → sum = 2 ✓
  [1, 2, -1] at indices 0-2 → sum = 2 ✓

Correct count = 2 (not 1!)

Key Observation: Use Prefix Sum Difference

For subarray from index i+1 to j to have sum = k:
  prefixSum[j] - prefixSum[i] = k

Rearrange:
  prefixSum[i] = prefixSum[j] - k

So we need to find:
  How many times have we seen (currentSum - k) before?

The Insight: Count Previous Occurrences

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

Calculate prefix sums and check:

Index -1: prefixSum = 0
  map = {0: 1}

Index 0: nums[0] = 1, prefixSum = 1
  Looking for: 1 - 3 = -2
  map has -2? NO
  count = 0
  map = {0: 1, 1: 1}

Index 1: nums[1] = 2, prefixSum = 3
  Looking for: 3 - 3 = 0
  map has 0? YES, appears 1 time!
  count = 0 + 1 = 1 (subarray [1,2])
  map = {0: 1, 1: 1, 3: 1}

Index 2: nums[2] = 3, prefixSum = 6
  Looking for: 6 - 3 = 3
  map has 3? YES, appears 1 time!
  count = 1 + 1 = 2 (subarray [3])
  map = {0: 1, 1: 1, 3: 1, 6: 1}

Total count: 2 ✓

Why This Works - Mathematical Proof

We want subarrays with sum = k

If prefixSum[j] - prefixSum[i] = k:
  Then subarray from i+1 to j has sum = k ✓

Rearranging:
  prefixSum[i] = prefixSum[j] - k

At position j:
  currentSum = prefixSum[j]
  targetSum = currentSum - k

Count = how many times we've seen targetSum before!

Why count occurrences?
  Each occurrence of targetSum represents one valid subarray
  that ends at current position!

🚨 Why Count Frequency (Not Just Check Existence)?

CRITICAL: This is different from problems #50 and #51!

nums = [1, -1, 1, -1, 1], k = 0

Prefix sums:
Index:  -1  0   1   2   3   4
Prefix:  0  1   0   1   0   1

prefixSum = 0 appears at: -1, 1, 3
prefixSum = 1 appears at: 0, 2, 4

At index 1 (prefixSum = 0):
  Looking for: 0 - 0 = 0
  Found 1 time (at index -1)
  count += 1 → Subarray [1, -1]

At index 3 (prefixSum = 0):
  Looking for: 0 - 0 = 0
  Found 2 times! (at indices -1 and 1)
  count += 2 → Subarrays [1,-1,1,-1] and [1,-1]

We need FREQUENCY, not just existence!
Each previous occurrence creates one valid subarray!

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all subarrays:
1. For each starting position i
2. For each ending position j
3. Calculate sum of subarray [i, j]
4. If sum equals k, increment count

Implementation

public int subarraySum(int[] nums, int k) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum == k) {
                count++;
            }
        }
    }

    return count;
}

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - only variables

🎯 Approach 2: Prefix Sum Array

Better Approach 💡

Core Logic:

Use prefix sum to get any subarray sum in O(1):

1. Build prefix sum array
2. Check all pairs (i, j)
3. If prefixSum[j] - prefixSum[i] = k, increment count

Key insight:
  sum(i+1 to j) = prefixSum[j] - prefixSum[i]

Implementation

public int subarraySum(int[] nums, int k) {
    int n = nums.length;
    int count = 0;

    // Build prefix sum array
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // Check all pairs
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (prefixSum[j] - prefixSum[i] == k) {
                count++;
            }
        }
    }

    return count;
}

⏰ Time: O(n²) - checking all pairs
💾 Space: O(n) - prefix sum array

✅ Approach 3: HashMap with Running Sum (Optimal)

The Ultimate Optimization 💡

Core Logic:

Use HashMap to count prefix sum frequencies:

Key insight:
  If prefixSum[j] - prefixSum[i] = k
  Then prefixSum[i] = prefixSum[j] - k

Algorithm:
1. Track running sum
2. For each position, check: (currentSum - k)
3. Add frequency of (currentSum - k) to count
4. Update frequency of currentSum in map

Visual Explanation:

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

Running sum with HashMap:

map = {0: 1}  // Initialize
sum = 0
count = 0

Index 0: nums[0] = 1
  sum = 0 + 1 = 1
  target = 1 - 3 = -2
  count += map.getOrDefault(-2, 0) = 0
  map.put(1, 1)
  map = {0: 1, 1: 1}

Index 1: nums[1] = 2
  sum = 1 + 2 = 3
  target = 3 - 3 = 0
  count += map.getOrDefault(0, 0) = 1
  count = 1
  map.put(3, 1)
  map = {0: 1, 1: 1, 3: 1}

  Found: subarray [1, 2] with sum 3

Index 2: nums[2] = 3
  sum = 3 + 3 = 6
  target = 6 - 3 = 3
  count += map.getOrDefault(3, 0) = 1
  count = 2
  map.put(6, 1)
  map = {0: 1, 1: 1, 3: 1, 6: 1}

  Found: subarray [3] with sum 3

Total count: 2 ✓

Implementation

public int subarraySum(int[] nums, int k) {
    // Map: prefixSum -> frequency (how many times seen)
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: sum 0 appears once (before any elements)
    map.put(0, 1);

    int sum = 0;
    int count = 0;

    for (int num : nums) {
        sum += num;

        // Check if (sum - k) exists
        // Each occurrence represents one valid subarray
        int target = sum - k;
        count += map.getOrDefault(target, 0);

        // Update frequency of current sum
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }

    return count;
}

⏰ Time: O(n) - single pass
💾 Space: O(n) - hashmap stores prefix sums

🔍 Step-by-Step Execution

Approach 2 (Prefix Sum Array): nums = [1, -1, 2], k = 2

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, -1, 2], k = 2
n = 3


STEP 1: Build Prefix Sum Array
═══════════════════════════════════════════════════════════════════

prefixSum[0] = 0

i=0: nums[0] = 1
  prefixSum[1] = 0 + 1 = 1

i=1: nums[1] = -1
  prefixSum[2] = 1 + (-1) = 0

i=2: nums[2] = 2
  prefixSum[3] = 0 + 2 = 2

Final prefixSum array:
  Index:  0  1  2  3
  Prefix: 0  1  0  2


STEP 2: Check All Pairs for Difference = k
═══════════════════════════════════════════════════════════════════

i=0: prefixSum[0] = 0
───────────────────────────────────────────────────────────────────
  j=1: prefixSum[1] - prefixSum[0] = 1 - 0 = 1 ≠ 2 ✗
  j=2: prefixSum[2] - prefixSum[0] = 0 - 0 = 0 ≠ 2 ✗
  j=3: prefixSum[3] - prefixSum[0] = 2 - 0 = 2 = 2 ✓
       count = 1
       Subarray [1, -1, 2] from indices 0-2

i=1: prefixSum[1] = 1
───────────────────────────────────────────────────────────────────
  j=2: prefixSum[2] - prefixSum[1] = 0 - 1 = -1 ≠ 2 ✗
  j=3: prefixSum[3] - prefixSum[1] = 2 - 1 = 1 ≠ 2 ✗

i=2: prefixSum[2] = 0
───────────────────────────────────────────────────────────────────
  j=3: prefixSum[3] - prefixSum[2] = 2 - 0 = 2 = 2 ✓
       count = 2
       Subarray [2] from index 2


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 2
═══════════════════════════════════════════════════════════════════

Valid subarrays:
  [1, -1, 2] with sum 2
  [2] with sum 2

Approach 3 (HashMap): nums = [1, 1, 1], k = 2

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, 1, 1], k = 2
map = {0: 1}
sum = 0
count = 0


Index 0: nums[0] = 1
═══════════════════════════════════════════════════════════════════
sum = 0 + 1 = 1

Looking for: sum - k = 1 - 2 = -1
Check map for -1: NOT found
  count += 0 = 0

Update map with sum = 1:
  map.put(1, 1)
  map = {0: 1, 1: 1}

count = 0


Index 1: nums[1] = 1
═══════════════════════════════════════════════════════════════════
sum = 1 + 1 = 2

Looking for: sum - k = 2 - 2 = 0
Check map for 0: FOUND with frequency 1!
  count += 1 = 1

  This represents subarray [1, 1] from indices 0-1 ✓

Update map with sum = 2:
  map.put(2, 1)
  map = {0: 1, 1: 1, 2: 1}

count = 1


Index 2: nums[2] = 1
═══════════════════════════════════════════════════════════════════
sum = 2 + 1 = 3

Looking for: sum - k = 3 - 2 = 1
Check map for 1: FOUND with frequency 1!
  count += 1 = 2

  This represents subarray [1, 1] from indices 1-2 ✓

Update map with sum = 3:
  map.put(3, 1)
  map = {0: 1, 1: 1, 2: 1, 3: 1}

count = 2


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 2
═══════════════════════════════════════════════════════════════════

Valid subarrays:
  [1, 1] from indices 0-1
  [1, 1] from indices 1-2

Approach 3 (HashMap) - CRITICAL Example: nums = [1, -1, 1, -1, 1], k = 0

This example demonstrates WHY we need to track FREQUENCY!

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1, -1, 1, -1, 1], k = 0
map = {0: 1}
sum = 0
count = 0


Index 0: nums[0] = 1
═══════════════════════════════════════════════════════════════════
sum = 1

Looking for: 1 - 0 = 1
map has 1? NO
count = 0

map.put(1, 1)
map = {0: 1, 1: 1}


Index 1: nums[1] = -1
═══════════════════════════════════════════════════════════════════
sum = 1 + (-1) = 0

Looking for: 0 - 0 = 0
map has 0? YES, frequency = 1!
count += 1 = 1

🔑 Found subarray [1, -1] with sum 0

map.put(0, 2)  // Increment frequency!
map = {0: 2, 1: 1}


Index 2: nums[2] = 1
═══════════════════════════════════════════════════════════════════
sum = 0 + 1 = 1

Looking for: 1 - 0 = 1
map has 1? YES, frequency = 1!
count += 1 = 2

🔑 Found subarray [1] at index 2 with sum 0
   (Actually this is wrong, let me recalculate...)

Wait, sum at index 2 is 1, looking for 1-0=1
This finds subarray from previous sum=1 to current
Previous sum=1 was at index 0
Subarray from index 1 to 2: [-1, 1] with sum 0 ✓

map.put(1, 2)  // Increment frequency!
map = {0: 2, 1: 2}


Index 3: nums[3] = -1
═══════════════════════════════════════════════════════════════════
sum = 1 + (-1) = 0

Looking for: 0 - 0 = 0
map has 0? YES, frequency = 2!
count += 2 = 4

🔑 🚨 CRITICAL: We add 2, not 1!
   This represents 2 different subarrays:
   1. From index -1 to 3: [1, -1, 1, -1] ✓
   2. From index 1 to 3: [1, -1] ✓

map.put(0, 3)  // Increment frequency!
map = {0: 3, 1: 2}


Index 4: nums[4] = 1
═══════════════════════════════════════════════════════════════════
sum = 0 + 1 = 1

Looking for: 1 - 0 = 1
map has 1? YES, frequency = 2!
count += 2 = 6

🔑 🚨 CRITICAL: We add 2, not 1!
   This represents 2 different subarrays ending at index 4

map.put(1, 3)
map = {0: 3, 1: 3}


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: count = 6
═══════════════════════════════════════════════════════════════════

All subarrays with sum = 0:
  [1, -1] at indices 0-1
  [-1, 1] at indices 1-2
  [1, -1, 1, -1] at indices 0-3
  [1, -1] at indices 2-3
  [-1, 1, -1, 1] at indices 1-4
  [1, -1, 1] at indices 2-4

🚨 KEY INSIGHT:
═══════════════════════════════════════════════════════════════════

If we only tracked EXISTENCE (like problems #50, #51):
  We'd know "sum 0 exists" but not HOW MANY times!

By tracking FREQUENCY:
  We count ALL subarrays correctly!

This is why we use:
  count += map.getOrDefault(target, 0);  // Add frequency
  map.put(sum, map.getOrDefault(sum, 0) + 1);  // Increment

🔍 Edge Cases

Case 1: Single element equals k
Input: nums = [5], k = 5
Output: 1
Explanation: The element itself

Case 2: No valid subarray
Input: nums = [1, 2, 3], k = 10
Output: 0

Case 3: Multiple subarrays
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: [1,1] at 0-1 and [1,1] at 1-2

Case 4: Negative numbers
Input: nums = [1, -1, 0], k = 0
Output: 3
Explanation: [-1,1], [0], [1,-1,0]

Case 5: All elements sum to k
Input: nums = [1, 2, 3], k = 6
Output: 1

Case 6: k = 0
Input: nums = [0, 0, 0], k = 0
Output: 6
Explanation: [0], [0], [0], [0,0], [0,0], [0,0,0]

Case 7: Duplicate sums
Input: nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7
Output: 4

Case 8: Large array
Input: nums = [1]*20000, k = 5
Output: Count all subarrays of length 5

Common Mistakes

Mistake 1: Not initializing map with {0: 1}
❌ Wrong: 
    Map<Integer, Integer> map = new HashMap<>();
✓ Right: 
    map.put(0, 1);
Reason: Handles subarrays starting from index 0

Mistake 2: Only storing existence (not frequency)
❌ Wrong: 
    map.put(sum, 1);  // Always 1
✓ Right: 
    map.put(sum, map.getOrDefault(sum, 0) + 1);
Reason: Need to count ALL occurrences

Mistake 3: Checking if sum equals k directly
❌ Wrong: 
    if (sum == k) count++;
✓ Right: 
    count += map.getOrDefault(sum - k, 0);
Reason: Misses subarrays not starting from index 0

Mistake 4: Wrong target calculation
❌ Wrong: 
    int target = k - sum;
✓ Right: 
    int target = sum - k;
Reason: We want prefixSum[i] = prefixSum[j] - k

Mistake 5: Updating map before counting
❌ Wrong: 
    map.put(sum, map.getOrDefault(sum, 0) + 1);
    count += map.getOrDefault(sum - k, 0);
✓ Right: 
    count += map.getOrDefault(sum - k, 0);
    map.put(sum, map.getOrDefault(sum, 0) + 1);
Reason: Must count first, then update

Mistake 6: Using map.get() without checking
❌ Wrong: 
    count += map.get(sum - k);  // NullPointerException
✓ Right: 
    count += map.getOrDefault(sum - k, 0);
Reason: Target may not exist in map

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Prefix Sum Array
  Time: O(n²)
  Space: O(n)
  Use: Learning step

Approach 3: HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(n)
  Use: Optimal solution

🔑 The Core Insight

🚨 MOST IMPORTANT CONCEPTS
═══════════════════════════════════════════════════════════════

1. Don't Just Check if Sum Equals k:
───────────────────────────────────────────────────────────────

Wrong approach:
  if (sum == k) count++;

This only finds subarrays starting from index 0!

Example that breaks it:
  nums = [1, 2, 3], k = 3

  sum at index 1 = 3 → count [1,2] ✓
  But misses [3] at index 2 ✗


2. Check for (sum - k) in HashMap:
───────────────────────────────────────────────────────────────

Correct approach:
  count += map.getOrDefault(sum - k, 0);

Why sum - k?
  If prefixSum[j] - prefixSum[i] = k
  Then prefixSum[i] = prefixSum[j] - k

  At position j:
    currentSum = prefixSum[j]
    target = sum - k = prefixSum[i]

  Find how many times we've seen target!


3. Track FREQUENCY, Not Just Existence:
───────────────────────────────────────────────────────────────

This is different from problems #50 and #51!

Problem #50: Check if exists → return boolean
Problem #51: Find max length → store first index
Problem #52: Count subarrays → store frequency!

Example:
  nums = [1, -1, 1, -1], k = 0

  sum = 0 appears 3 times (indices -1, 1, 3)

  At index 3 (sum = 0):
    Looking for 0 - 0 = 0
    Found 2 times before!
    This means 2 subarrays end here:
      1. From index -1 to 3
      2. From index 1 to 3

  We need frequency to count all!


Mathematical Relationship:
═══════════════════════════════════════════════════════════════

Goal: Find subarrays with sum = k

If prefixSum[j] - prefixSum[i] = k:
  Then subarray from i+1 to j has sum k ✓

Rearrange:
  prefixSum[i] = prefixSum[j] - k

At position j:
  currentSum = prefixSum[j]
  target = currentSum - k = prefixSum[i]

Count all previous occurrences of target!

Why Frequency Matters:
═══════════════════════════════════════════════════════════════

Each occurrence of target represents one subarray:

If target appeared 3 times:
  3 different starting positions
  All end at current position
  = 3 valid subarrays!

Algorithm Pattern:
═══════════════════════════════════════════════════════════════

1. Initialize: map = {0: 1}, sum = 0, count = 0
2. For each element:
   a. sum += element
   b. target = sum - k
   c. count += map.getOrDefault(target, 0)
   d. map.put(sum, map.getOrDefault(sum, 0) + 1)
3. Return count

Order Matters!
═══════════════════════════════════════════════════════════════

Must count BEFORE updating map:

✓ Right order:
  count += map.get(sum - k)  // Count first
  map.put(sum, freq + 1)     // Then update

✗ Wrong order:
  map.put(sum, freq + 1)     // Update first
  count += map.get(sum - k)  // Then count

Why? Avoid counting current position as previous occurrence!

🎯 Pattern Recognition

Problem Type: Count Subarrays with Target Sum
Core Pattern: Prefix Sum + HashMap Frequency

When to Apply:
✓ Count number of subarrays
✓ Sum equals specific value
✓ Contiguous elements
✓ Can have negative numbers

Recognition Keywords:
- "Total number"
- "Count subarrays"
- "Sum equals"
- "Contiguous"

Comparison with Similar Problems:
┌──────────────────────────────────────────────────────┐
│ #50: Sum divisible by k                             │
│      Track: sum % k                                 │
│      Return: boolean (exists or not)                │
│                                                      │
│ #51: Equal 0s and 1s                                │
│      Track: balance (0→-1)                          │
│      Return: int (max length)                       │
│      Store: First occurrence                        │
│                                                      │
│ #52: Sum equals k                                   │
│      Track: prefix sum                              │
│      Return: int (count)                            │
│      Store: FREQUENCY                               │
└──────────────────────────────────────────────────────┘

All use prefix sum + HashMap, but different goals!

🧠 Interview Strategy

Step 1: "Count subarrays with sum equals k"
Step 2: "Use prefix sum concept"
Step 3: "If prefixSum[j] - prefixSum[i] = k, rearrange to get target"
Step 4: "target = currentSum - k"
Step 5: "Count how many times we've seen target"
Step 6: "Use HashMap to store frequency"
Step 7: "Add frequency to count, then update map"
Step 8: "O(n) time, O(n) space"

Key Points to Mention:
- Recognize prefix sum pattern
- Explain why sum - k (not just sum = k)
- Emphasize frequency tracking (not just existence)
- HashMap stores sum → frequency
- Initialize {0: 1} for edge cases
- Count before updating map
- Handles negative numbers naturally
- Time: O(n), Space: O(n)
- Single pass solution

Why HashMap Frequency?
"Unlike finding if a subarray exists or finding max length,
this problem asks to COUNT all valid subarrays. Each time
I've seen (currentSum - k) before represents one valid
subarray ending at the current position. So I need to
track how many times each sum has appeared, not just
whether it exists or where it first appeared."

Why Order Matters?
"I count first, then update the map. This prevents
counting the current position as a previous occurrence,
which would incorrectly include empty subarrays."

This is a classic prefix sum + HashMap problem! 🏆

📝 Quick Revision Notes

🎯 Core Concept:

🚨 CRITICAL: Track FREQUENCY, not just existence! Find sum - k in HashMap. Each occurrence = one subarray. Count before updating map!

Why Not Just Check sum == k?

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

Only checking sum == k: misses [3] at index 2!
Must check for (sum - k) to find ALL subarrays!

Why Track Frequency?

nums = [1,-1,1,-1], k = 0

sum = 0 appears 3 times
Each occurrence represents different subarrays!
Need frequency to count all!

⚡ Quick Implementation:

import java.util.HashMap;

class Test {
  public int subarraySum(int[] a, int k) {
    int res = 0;
    int len = a.length;
    // // Approach 1 - using prefixsum alone
    // // Sum of any subarray (i, j) = prefix[j] - prefix[i] (ignore i+1 / j+1 for now)
    // // which is k (for example). Now, we need to count number of such subarrays
    // // whose sum is k for every (i, j) (have to calculate prefix[j] - prefix[i])
    // // Derive prefixsum
    // int[] prefixsum = new int[len + 1];
    // for (int i = 1; i <= len; i++) {
    //   prefixsum[i] = prefixsum[i - 1] + a[i - 1];
    // }
    // for (int i = 0; i <= len; i++) {
    //   for (int j = i + 1; j <= len; j++) {
    //     if (prefixsum[j] - prefixsum[i] == k) {
    //       res++;
    //     }
    //   }
    // }

    // Approach 2 - using runningsum and hashmap
    int sum = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    // This accounts for subarrays that start at index 0. If at some index i, sum == k, 
    // then sum - k == 0, and the map tells us there’s one way (using the empty prefix) to make that subarray.
    map.put(0, 1);
    for(int i = 0; i < len; i++) {
      sum = sum + a[i];

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

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


    return res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.subarraySum(new int[] { 5 }, 5));
    System.out.println(t.subarraySum(new int[] { 1, 2, 3 }, 3));
    System.out.println(t.subarraySum(new int[] { 1, 2, 3 }, 10));
    System.out.println(t.subarraySum(new int[] { 1, 1, 1 }, 2));
    System.out.println(t.subarraySum(new int[] { 1, -1, 0 }, 0));
    System.out.println(t.subarraySum(new int[] { 0, 0, 0 }, 0));
    System.out.println(t.subarraySum(new int[] { 3, 4, 7, 2, -3, 1, 4, 2 }, 7));
    System.out.println(t.subarraySum(new int[] { -1, -1, 1 }, 0));
  }
}

🔑 Key Insights:

🚨 CRITICAL: Store FREQUENCY (not just existence/first index)
Pattern: Prefix sum + HashMap frequency counting
Formula: target = sum - k (not sum = k!)
Why: prefixSum[i] = prefixSum[j] - k for subarray sum = k
HashMap: Maps sum → frequency (count of occurrences)
Initialize: {0: 1} handles subarrays from start
Order: Count BEFORE updating map (critical!)
Goal: COUNT all valid subarrays (not find/exists)
Handles: Negative numbers naturally
Time: O(n) - single pass
Space: O(n) - store all unique sums

🎪 Memory Aid:

"Count all! Track FREQUENCY! Find (sum - k), count how many times!"
Think: "Each previous occurrence = one subarray!"

💡 The Key Formula:

prefixSum[j] - prefixSum[i] = k
Rearrange:
  prefixSum[i] = prefixSum[j] - k

At position j:
  currentSum = prefixSum[j]
  target = currentSum - k
  count = frequency of target

🔥 Why This Works:

If sum - k appeared 3 times before:
  3 different starting positions
  All ending at current position
  = 3 valid subarrays!

Add all frequencies = total count!

⚠️ Critical Details:

1. Initialize: map.put(0, 1)
2. Target: sum - k (not k - sum)
3. Count first: count += map.get(target)
4. Then update: map.put(sum, freq + 1)
5. Use getOrDefault to avoid null
6. Track frequency (not boolean/index)

🎯 Pattern Comparison:

#50: Divisible → Track remainder → Return boolean
#51: Equal 0/1 → Track balance → Return max length → Store first index
#52: Sum = k → Track sum → Return count → Store FREQUENCY

Same HashMap pattern, different storage!

Continuous Subarray Sum (LC 523) - Problem #50
Contiguous Array (LC 525) - Problem #51
Subarray Product Less Than K (LC 713)
Maximum Size Subarray Sum Equals k (LC 325)

Happy practicing! 🎯

52. Subarray Sum Equals K

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Read This Carefully!

Key Observation: Use Prefix Sum Difference

The Insight: Count Previous Occurrences

Why This Works - Mathematical Proof

🚨 Why Count Frequency (Not Just Check Existence)?

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Prefix Sum Array

Better Approach 💡

Implementation

✅ Approach 3: HashMap with Running Sum (Optimal)

The Ultimate Optimization 💡

Implementation

🔍 Step-by-Step Execution

Approach 2 (Prefix Sum Array): nums = [1, -1, 2], k = 2

Approach 3 (HashMap): nums = [1, 1, 1], k = 2

Approach 3 (HashMap) - CRITICAL Example: nums = [1, -1, 1, -1, 1], k = 0

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns