Code Logo

Subarray Sum Equals K

Published at16 Mar 2026
Created by
Medium 45 views
Like0

You are given an array and a target value k. The goal is to count how many contiguous subarrays have sum exactly equal to k.

This is important: the subarray must be continuous. Also, the answer is a count, not the longest length and not the actual subarrays themselves.

For example, if nums = [1,1,1] and k = 2, the answer is 2 because the subarrays [1,1] at positions (0,1) and (1,2) both work. If nums = [1,2,3] and k = 3, the answer is 2 because both [1,2] and [3] match.

So the task is to count every continuous segment whose total is exactly k.

Example Input & Output

Example 1
Input
nums = [1,1,1], k = 2
Output
2
Explanation

Subarrays [1,1] at positions (0,1) and (1,2).

Example 2
Input
nums = [1,2,3], k = 3
Output
2
Explanation

Subarrays [1,2] and [3].

Example 3
Input
nums = [1,-1,0], k = 0
Output
3
Explanation

Subarrays [1,-1], [0], and [1,-1,0].

Algorithm Flow

Recommendation Algorithm Flow for Subarray Sum Equals K
Recommendation Algorithm Flow for Subarray Sum Equals K

Solution Approach

The standard hash table solution uses prefix sums. Let prefix mean the sum of all numbers from the start of the array up to the current position.

If a subarray from index j + 1 to i has sum k, then:

prefix[i] - prefix[j] = k

Rearranging that gives:

prefix[j] = prefix[i] - k

That is the key idea. While scanning the array, if the current prefix sum is prefix, then any earlier prefix sum equal to prefix - k creates a valid subarray ending at the current index.

So we keep a map from prefix sums to how many times each one has appeared so far. Before the loop starts, set map[0] = 1 so subarrays starting at index 0 are counted correctly.

At each number, update the running prefix sum, add map[prefix - k] to the answer if it exists, then record the new prefix sum in the map.

This works even with negative numbers, which is why it is better than a simple sliding window here. The time complexity is O(n), and the extra space is O(n) in the worst case.

Best Answers

java
import java.util.*;
class Solution {
    public int subarray_sum_equals_k(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int s = 0, ans = 0;
        for (int x : nums) {
            s += x;
            ans += count.getOrDefault(s - k, 0);
            count.put(s, count.getOrDefault(s, 0) + 1);
        }
        return ans;
    }
}