Subarray Sum Equals K

Medium Arrays

Count the number of contiguous subarrays that sum to k, using prefix sums stored in a hash map.

Sample input

[1, 1, 1], k = 2

Sample output

Solution

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}
    for num in nums:
        prefix += num
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

print(subarray_sum([1, 1, 1], 2))

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);
  let count = 0, prefix = 0;
  for (const num of nums) {
    prefix += num;
    count += seen.get(prefix - k) || 0;
    seen.set(prefix, (seen.get(prefix) || 0) + 1);
  }
  return count;
}

console.log(subarraySum([1, 1, 1], 2));

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int count = 0, prefix = 0;
        for (int num : nums) {
            prefix += num;
            count += seen.getOrDefault(prefix - k, 0);
            seen.merge(prefix, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{1, 1, 1}, 2));
    }
}

fun subarraySum(nums: IntArray, k: Int): Int {
    val seen = HashMap<Int, Int>()
    seen[0] = 1
    var count = 0
    var prefix = 0
    for (num in nums) {
        prefix += num
        count += seen.getOrDefault(prefix - k, 0)
        seen[prefix] = seen.getOrDefault(prefix, 0) + 1
    }
    return count
}

fun main() {
    println(subarraySum(intArrayOf(1, 1, 1), 2))
}

func subarraySum(_ nums: [Int], _ k: Int) -> Int {
    var seen = [0: 1]
    var count = 0, prefix = 0
    for num in nums {
        prefix += num
        count += seen[prefix - k, default: 0]
        seen[prefix, default: 0] += 1
    }
    return count
}

print(subarraySum([1, 1, 1], 2))

int subarraySum(List<int> nums, int k) {
  final seen = <int, int>{0: 1};
  int count = 0, prefix = 0;
  for (final num in nums) {
    prefix += num;
    count += seen[prefix - k] ?? 0;
    seen[prefix] = (seen[prefix] ?? 0) + 1;
  }
  return count;
}

void main() {
  print(subarraySum([1, 1, 1], 2));
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<int, int> seen;
    seen[0] = 1;
    int count = 0, prefix = 0;
    for (int num : nums) {
        prefix += num;
        auto it = seen.find(prefix - k);
        if (it != seen.end()) count += it->second;
        seen[prefix]++;
    }
    return count;
}

int main() {
    cout << subarraySum({1, 1, 1}, 2) << endl;
    return 0;
}

#include <stdio.h>

int subarraySum(int *nums, int n, int k) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

int main() {
    int nums[] = {1, 1, 1};
    printf("%d\n", subarraySum(nums, 3, 2));
    return 0;
}