起因
今天做了一道题，LeetCode 560. Subarray Sum Equals K，有点蒙蔽，看了答案发现比较简单，记录一下
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
1
2
3
4
5
6
7
8
| 示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
|
题解
题目的意思比较明确，要求找到 n 个连续的子数组，并且这些连续子数组的和为 k
- 子数组求和
- 子数组求和可以使用前缀和，那么如何知道它能够满足需求? 前缀和可以知道具体区间的和，那么区间终点的值 -k，就是这段区间的起点。
- 需要一个哈希表，来记录上次出现该值得地方，找到
cur-k 就是找到了和位 k 的区间起点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int subArraySum(vector<int> &nums, int k) {
int ans = 0, pre = 0;
unordered_map<int, int> memo_;
memo_[0] = 1;
for (const auto &num : nums) {
pre += num;
if (memo_.find(pre - k) != memo_.end()) {
ans += memo_[pre - k];
}
memo_[pre]++;
}
return ans;
}
};
|
