1.题目介绍
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
2.题解
请注意题目中要求的连续非空序列,要求1.连续 2.非空!!!
2.1 枚举(O(n^2))
思路
最简单的思路是利用双重循环确定数组的开头和结尾,在利用一重循环来进行遍历相加
int count = 0;
for (int start = 0; start <= nums.size(); start++)
{
for (int end = start; end <= nums.size(); end++)
{
int sum = 0;
for (int i = start; i <= end; i++)
sum += nums[i];
if (sum == k) count++;
}
}
但是这里的时间复杂度达到了O(n^3),必定会超过限制,所以我们进行了一些优化
还是双重循环遍历,确定数组的两个端点
但每次并非从前向后,而是从后向前挨个相加检查。
start确定遍历子数组的右端点,这里end为何不是从0开始,而是从start开始呢?
这样有一个什么好处呢,就是我们每次都有着[j,i]的和
只要再加上nums[j-1],就可以再得到[j-1,i]。
如果end从0开始,其实就和上面的三重循环遍历没有区别了
题解
注意这里找到 sum == k的时候,不可以直接break,因为举个例子[-1,1,0] k = 0; 这时候start指向0这个数,发现sum = k直接break,子数组[-1,1,0]也满足条件但是没有算上!!!
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for (int start = 0; start < nums.size(); start++) {
int sum = 0;
for (int end = start; end >= 0; end--) {
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
};
2.2 前缀和 + 哈希表优化
思路
关于前缀和是啥,请参考:前缀和
即 存在:preSum[i] = preSum[i-1] + nums[i]
前缀和 就是从 nums 数组中的第 0 位置开始,累加到第 i 位置的结果,我们常把这个结果保存到数组 preSum 中,记为 preSum[i]。
降二重循环为一重循环:
我们可以基于方法一利用数据结构进行进一步的优化,我们知道方法一的瓶颈在于对每个 i,我们需要枚举所有的 j 来判断是否符合条件,所以可以优化为一重循环吗?
我们既然选用一重循环,就面临一个问题,我们只能确定一个参数,这里我们肯定选择区间的右端点,这样的话我们怎么知道其与另一端点构成的子数组和呢?
这里我们利用前缀和的思路去做即可,即我们需要一个数组或者哈希表来保存之前求得的和,即[0,i-1]的和。
这里还有一个问题:子数组可能不是从下标0开始,也有可能是[j,i], 也就是 preSum[i] - preSum[j] = k;
那换个思路是不是我只要用哈希表存储了[0,i-1]每个0开始子数组{如[0,0],[0,1],[0,2]...}的前缀和和其出现次数,
并且加上一个用于表示[0,i]这个数组的键值对{0,1} [preSum[i] -preSum[0]表示的是[1,i],这里我必须加上这个键值对,preSum[i]-0表示的才是[0,i]的值]。
在得到preSum[i] = preSum[i-1] + nums[i]后,由preSum[i] - preSum[j] = k;演变为preSum[j] = preSum[i] - k; 寻找哈希表中值为preSum[i] - k的存在及其出现次数,若存在,将count加上出现次数;不存在,继续遍历即可。
但我们再仔细想想,已经使用了哈希表存储了前缀和及其出现次数,我们还需要用preSum数组来存储前缀和吗?明显是不需要的,我们只需要维护一个前缀和变量pre即可
这里不使用数组存储也是考虑到数组无法快速记录出现次数的问题
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
int count = 0, pre = 0;
mp[0] = 1;
for (int i = 0; i < nums.size(); i++){
pre += nums[i];
if (mp.count(pre - k)) count += mp[pre-k];
mp[pre]++;
}
return count;
}
};
标签:count,start,560,nums,int,数组,preSum
From: https://www.cnblogs.com/trmbh12/p/17972778