Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Subarray Sum Equals K

Medium · Arrays · Asked at Google, Amazon, Microsoft, Meta

Count the number of contiguous subarrays whose sum is exactly k.

Input

First line: n. Second line: n integers. Third line: k.

Output

The number of subarrays with sum k.

Constraints

Prefix sums + hash map of how often each prefix sum appeared.

Example 1

Input

3
1 1 1
2

Output

2

Example 2

Input

3
1 2 3
3

Output

2

Hints

  1. The sum of a[i..j] equals prefix[j] − prefix[i − 1].
  2. While scanning, count how many earlier prefix sums equal currentPrefix − k (use a hash map of counts).

Approach

A subarray ending at j has sum k exactly when some earlier prefix sum equals prefix[j] − k. Keep a hash map from prefix sum to how many times it has appeared, starting with {0: 1} for the empty prefix. At every index, add count[prefix − k] to the answer, then record the current prefix. Negative numbers are why a sliding window doesn't work here. The count can reach about n²/2, so use 64 bits.

Complexity: O(n) average time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long k;
    cin >> k;
    unordered_map<long long, long long> seen;
    seen[0] = 1;
    long long prefix = 0, count = 0;
    for (long long x : a) {
        prefix += x;
        auto it = seen.find(prefix - k);
        if (it != seen.end()) count += it->second;
        seen[prefix]++;
    }
    cout << count << "\n";
    return 0;
}

Python solution

import sys
from collections import defaultdict

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
seen = defaultdict(int)
seen[0] = 1
prefix = count = 0
for x in a:
    prefix += x
    count += seen[prefix - k]
    seen[prefix] += 1
print(count)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        long k = sc.nextLong();
        Map<Long, Long> seen = new HashMap<>();
        seen.put(0L, 1L);
        long prefix = 0, count = 0;
        for (long x : a) {
            prefix += x;
            count += seen.getOrDefault(prefix - k, 0L);
            seen.merge(prefix, 1L, Long::sum);
        }
        System.out.println(count);
    }
}

Solve Subarray Sum Equals K online · All practice problems