Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2 Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
Companies:
Facebook, Bloomberg, Amazon, Twilio, Apple, Microsoft, Yandex, Expedia
Related Topics:
Array, Hash Table
Similar Questions:
- Two Sum (Easy)
- Continuous Subarray Sum (Medium)
- Subarray Product Less Than K (Medium)
- Find Pivot Index (Easy)
- Subarray Sums Divisible by K (Medium)
// OJ: https://leetcode.com/problems/subarray-sum-equals-k/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0, sum = 0;
unordered_map<int, int> m{{0, 1}};
for (int n : nums) {
sum += n;
auto it = m.find(sum - k);
if (it != m.end()) ans += it->second;
m[sum]++;
}
return ans;
}
};