Subarray sum equals k

Problem Link

560. Subarray Sum Equals K – LeetCode

Problem Statement

You are given an integer array 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.

Examples

Example 1:

Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: Subarrays [1, 1] at indices [0,1] and [1,2] sum to 2.

Example 2:

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: Subarrays [1,2] and [3] sum to 3.

Constraints

• 1 <= nums.length <= 2 × 10⁴

• -1000 <= nums[i] <= 1000

• -10⁷ <= k <= 10⁷

Intuition

This is a classic prefix sum problem with a hashmap to track previously seen sums.

The core idea is:

If the cumulative sum up to index i is prefixSum and we know there's a previous prefix sum prefixSum - k,
then the subarray between those two indices must sum to k.

We count how many times we've seen the sum prefixSum - k before.

Approach

1. Initialize:

   • prefixSum = 0 → sum from 0 to current index

   • count = 0 → total valid subarrays found

   • map = {0: 1} → one empty prefix that sums to 0

2. Traverse the array:

   • Update prefixSum += nums[i]

   • Check if prefixSum - k exists in map:

     • If yes, add its frequency to count

   • Update the frequency of prefixSum in map

3. Return count

Java Code

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        int pre = 0;
        int count = 0;
        
        map.put(0, 1); // Base case: empty subarray has sum 0
        
        for (int i = 0; i < n; i++) {
            pre += nums[i];
            int remove = pre - k;
            count += map.getOrDefault(remove, 0);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        
        return count;
    }
}

Time and Space Complexity

Dry Run

Input:

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

Execution:

Key Observations

• prefixSum - k helps identify all previous prefixes which, if removed, would leave a sum of k.

• map.getOrDefault(remove, 0) accumulates frequency of valid starting points for subarrays.

• Using a hashmap allows us to count in constant time rather than scanning all subarrays.

Conclusion

This problem demonstrates the power of prefix sums + hashmaps in reducing subarray-sum problems from O(n²) brute force to O(n) optimal.

Use this pattern when:

• You're asked to count subarrays with a certain sum

• The array contains negative numbers, making sliding window invalid.