LeetCode560 和为k的子数组

链接: https://leetcode-cn.com/problems/subarray-sum-equals-k/

题意

给定一个数组,寻找和为 k 的连续区间个数。

解法

本来以为是个简单题 结果卡了快一下午
不过好歹还是学到点东西的 对前缀和理解更深了一点
有一些收获
本来以为前缀和是有序的,然后可以二分找到差值
结果调了很久发现行不通 因为前缀和并不是有序的 甚至还有可能有多个相同的值
白白浪费两个小时
暴力二重循环会在最后一个样例超时

然后考虑用map存储所有的前缀和和它们的下标,由于同一个值可能对应多个索引
所以需要用multimap存储 学习了一下multimap的用法
multimap找键值的时候不能用[]来进行访问 需要用equal_range函数找出所有key-pair
返回值是一个iterator的pair分别表示找到的头尾 再进行访问
如果出现的target在当前下标前就加到结果中
这样可以通过 但是效率很低

正确的方法是 不需要一下子存入所有的前缀和到map中
遍历的过程中 实时更新map键值 这样可以保证后面加进来的都是之前的前缀和
而不会出现后面的前缀和的情况

这样的做法下甚至可以不需要pre数组,只要一个变量存储前缀和就可以
这样解法下的代码很短 可以说是简洁而优雅

代码

multimap解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if (nums.empty()) return k == 0;
int n = nums.size(), cnt = 0;
vector<int> pre(n + 1);
multimap<int, int> mp;
mp.insert({0, 0});
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + nums[i - 1];
mp.insert({pre[i], i});
}
for (int i = 1; i <= n; i++) {
int target = pre[i] - k;
auto pr = mp.equal_range(target);
if(pr.first != mp.end())
{
for (auto iter = pr.first ; iter != pr.second; ++iter)
{
if (iter->second < i) {
cnt++;
}
if (iter->second > i) {
break;
}
}
}
}
return cnt;
}
};

前缀和数组解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if (nums.empty()) return k == 0;
int n = nums.size(), cnt = 0;
vector<int> pre(n + 1);
unordered_map<int, int> mp;
mp[0] = 1;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
cnt += mp[pre[i] - k];
mp[pre[i]]++;
}
return cnt;
}
};

最优解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
if (nums.empty()) return k == 0;
int n = nums.size(), cnt = 0, presum = 0;
unordered_map<int, int> mp;
mp[0] = 1;
for (int i = 1; i <= n; i++) {
presum += nums[i - 1];
cnt += mp[presum - k];
++mp[presum];
}
return cnt;
}
};