Problem 39: Subarray Sum Equals K
Problem Statement: Given an array of n integers and an integer k, count the number of contiguous subarrays that sum to k.
Input
The first line contains two integers n and k. The second line contains n space-separated integers.
Output
Print the number of subarrays whose sum equals k.
Examples
Input:
5 5
1 2 3 2 1
Output:
2
Solution in C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<int> a(n);
for (int i=0; i<n; i++) cin >> a[i];
unordered_map<int, long long> mp;
mp[0] = 1;
int prefix = 0;
long long ans = 0;
for (int i=0; i<n; i++){
prefix += a[i];
if(mp.find(prefix - k) != mp.end()) {
ans += mp[prefix - k];
}
mp[prefix]++;
}
cout << ans << "\n";
return 0;
}