medium
source: https://leetcode.com/problems/subarray-sum-equals-k
C/C++ Solution to LeetCode problem 560. Subarray Sum Equals K.
Problem
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Examples
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int cSum = 0;
unordered_map<int,int>m;
for (int i=0; i<nums.size(); i+=1) {
cSum += nums[i];
if (cSum == k)
count++;
if (m.find(cSum - k) != m.end())
count += m[cSum - k];
m[cSum]++;
}
return count;
}
};