mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
31 lines
1.1 KiB
Markdown
31 lines
1.1 KiB
Markdown
# [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)
|
||
|
||
# 思路
|
||
|
||
求和为k的连续子数组的个数。因为要求连续子数组，所以我们可以先计算出前缀和`preSum`，然后就可以很方便计算任意区间对应的连续子数组的和`sum[i~j] = preSum[j]-preSum[i]`。要和为k，所以我们可以用一个二重循环遍历前缀和数组`preSum`，但是复杂度为O(n^2)。
|
||
|
||
更高效的做法是用一个hash表来记录所有前缀和与其出现次数的映射，这样假设当前位置的累加和为`cur_sum`，我们可以通过哈希表快速查找`cur_sum - k`出现的次数。注意hash表初始时要有一个0到1的映射。
|
||
|
||
时间复杂度O(n)
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int subarraySum(vector<int>& nums, int k) {
|
||
unordered_map<int, int>mp;
|
||
mp[0] = 1;
|
||
|
||
int cur_sum = 0, res = 0;
|
||
for(int i = 0; i < nums.size(); i++){
|
||
cur_sum += nums[i];
|
||
auto it = mp.find(cur_sum - k);
|
||
if(it != mp.end()) res += it -> second;
|
||
mp[cur_sum]++;
|
||
}
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|