Subarray Sum Equals K

Hash Table Medium 30 views

Like0

Subarray Sum Equals K is basically a counting game: from an array nums, how many contiguous chunks add up exactly to k? You only return the count, not the chunks themselves.

The trick that makes this fast is prefix sum + frequency map. As you scan the array, keep a running total called prefix. At any position, if you already saw a prefix value of prefix - k, it means there is a valid subarray ending here. So you add that frequency to the answer.

Workflow is simple: check how many times prefix - k appeared, add it to result, then record the current prefix in the map. Start with freq[0] = 1 so subarrays starting from index 0 are counted correctly.

This works smoothly even with negative numbers and zeros, where two-pointer sliding window usually breaks. It is O(n) time, and it naturally handles overlapping subarrays too. The judge cases include mixed-sign arrays and lots of zero-based overlaps, so counting prefix frequencies (not just storing one index) is the key to getting the correct final number.

One small but important detail: the order is always read first, write second. If you store current prefix too early, you can accidentally count an invalid zero-length subarray. Keep that sequence clean, and this solution stays both fast and reliable on all judge tests.

Examples

Example 1

Input

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

Output

Explanation

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

Example 2

Input

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

Output

Explanation

Subarrays [1,2] and [3].

Example 3

Input

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

Output

Explanation

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

Algorithm Flow

Recommendation Algorithm Flow for Subarray Sum Equals K - Budibadu

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;
    }
}

javascript

function subarray_sum_equals_k(nums, k) {
    const count = {0: 1};
    let s = 0, ans = 0;
    for (let i = 0; i < nums.length; i++) {
        s += nums[i];
        const need = s - k;
        ans += (count[need] || 0);
        count[s] = (count[s] || 0) + 1;
    }
    return ans;
}

php

<?php
function subarray_sum_equals_k($nums, $k) {
    $count = ["0" => 1];
    $s = 0; $ans = 0;
    foreach ($nums as $x) {
        $s += $x;
        $need = (string)($s - $k);
        $ans += ($count[$need] ?? 0);
        $key = (string)$s;
        $count[$key] = ($count[$key] ?? 0) + 1;
    }
    return $ans;
}
?>

python

from typing import List

def subarray_sum_equals_k(nums: List[int], k: int) -> int:
    count = {0: 1}
    s = 0
    ans = 0
    for x in nums:
        s += x
        ans += count.get(s - k, 0)
        count[s] = count.get(s, 0) + 1
    return ans

rust

use std::collections::HashMap;
fn subarray_sum_equals_k(nums: Vec<i32>, k: i32) -> i32 {
    let mut count: HashMap<i32, i32> = HashMap::new();
    count.insert(0, 1);
    let mut s = 0;
    let mut ans = 0;
    for x in nums {
        s += x;
        ans += *count.get(&(s - k)).unwrap_or(&0);
        *count.entry(s).or_insert(0) += 1;
    }
    ans
}

typescript

function subarray_sum_equals_k(nums: number[], k: number): number {
    var count: { [key: string]: number } = {"0": 1};
    var s = 0, ans = 0;
    for (var i = 0; i < nums.length; i++) {
        s += nums[i];
        var need = String(s - k);
        ans += (count[need] || 0);
        var key = String(s);
        count[key] = (count[key] || 0) + 1;
    }
    return ans;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Subarray Sum Equals K

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion