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 Explanation
Method 1: Use a prefix sum array combined with a hash map to count the frequency of prefix sums and thereby count the number of valid subarrays in O(n) time. Method 2: A brute-force approach by checking all subarrays leads to O(n^2) time, which is only feasible for small arrays.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector a(n);
for (int i=0; i> a[i];
unordered_map mp;
mp[0] = 1;
int prefix = 0;
long long ans = 0;
for (int i=0; i