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
- 1 ≤ n ≤ 10^5
- -1000 ≤ a[i] ≤ 1000
- -10^7 ≤ k ≤ 10^7
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
- The sum of a[i..j] equals prefix[j] − prefix[i − 1].
- 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);
}
}