Algorithm-Day10-Subarray-Sum-Equals-K-lc-560

Posted on In , Views:

🧩 Problem Description

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

Example:

Input: nums = [1,1,1], k = 2
Output: 2

💡 Brute Force (Too Slow)

Try every subarray and compute its sum.

1
2
3
4
5
6
7
8
9
// Time: O(n^2)
int count = 0;
for (int start = 0; start < nums.length; start++) {
    int sum = 0;
    for (int end = start; end < nums.length; end++) {
        sum += nums[end];
        if (sum == k) count++;
    }
}
  • ❌ Time complexity: O(n²)
  • Works only for small inputs

💡 Optimized Approach: Prefix Sum + HashMap

✨ Key Insight

If we know the prefix sum up to index i is sum, and we previously saw a prefix sum of sum - k,
then the subarray between those two indices sums to k.

✅ Steps

  • Use a Map<Integer, Integer> to count how many times each prefix sum has occurred.
  • At each step:
    • Add current number to running sum
    • Check if sum - k has appeared before → it means a subarray with sum = k ends here
    • Add sum to the map

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1); // Important: one way to get sum = 0 before starting

        int sum = 0;
        int count = 0;

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

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

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

        return count;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n)
    One pass through the array
  • Space Complexity: O(n)
    For the prefix sum map

✍️ Summary

  • Prefix sum is a powerful technique for cumulative problems
  • The hash map tracks all possible sums we’ve seen so far
  • Key trick: initialize the map with {0:1} to handle cases where subarray starts at index 0

This is a high-frequency interview question and a foundation for other problems like Longest Subarray Sum, Count of Subarrays With Sum Divisible by K, etc.