Subarray Sum Equals K

Like0

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

The hash table trick is to track prefix sums and how often each sum has appeared. If current prefix is sum, then any previous prefix sum-k forms a valid subarray ending at the current index.

This turns a slow O(n^2) scan into O(n) using a map of prefix frequencies.

Example 1:

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

Example 2:

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

Example 3:

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

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

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