子串#中等#和为K的子数组
子串#中等#和为K的子数组
前文
给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。
子数组是数组中元素的连续非空序列。
1
2
3
4
5
6
7
8
9
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
正文
1
2
3
4
5
6
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
}
};
解法1
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, sum = 0;
for(auto n = 1; n <= nums.size(); ++n) {
for(auto i = 0; i < nums.size(); ++i) {
if (i+n > nums.size())
continue;
sum = 0;
for (auto j = i; j < i+n; ++j)
sum += nums[j];
if (sum == k)
++count;
}
}
return count;
}
};
暴力破解，遍历所有可能的情况，即计算n={1, 2, 3, ..., n}位的每个子串的值，但是这样会超出用时。
解法2
将已计算过的存储下来，这里用{下标,下标}表示两个下标之间元素的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
map<vector<int>, int> sumMap;
int count = 0, sum = 0;
for(auto n = 1; n <= nums.size(); ++n) {
for(auto i = 0; i < nums.size(); ++i) {
if (i+n > nums.size())
continue;
sum = 0;
if (sumMap[{i, i+n-2}]) {
sum = sumMap[{i, i+n-2}];
}
sum += nums[i+n-1];
sumMap[{i, i+n-1}] = sum;
if (sum == k)
++count;
}
}
return count;
}
};
还是会超时
本文由作者按照 CC BY 4.0 进行授权