挣钱做任务的网站,网站导航栏有哪些,涿鹿县建设局网站,南戴河区网站建设哪家好和为K的子数组链接 目录
第一步#xff1a;了解题意编辑
第二步#xff1a;算法原理
第三步#xff1a;代码 第一步#xff1a;了解题意
数组中和为k的连续子数组#xff0c;我们主要关注的是连续的#xff0c; 比如[1,1,1],和为2的子数组有俩个#xff0c;比如第…和为K的子数组链接 目录
第一步了解题意编辑
第二步算法原理
第三步代码 第一步了解题意
数组中和为k的连续子数组我们主要关注的是连续的 比如[1,1,1],和为2的子数组有俩个比如第一个1和第二个1还有第二个1和第三个1都是属于俩种不同的情况。
比如[1,2,3],123属于一组3也属于一组所以有俩组。
我们可以认为
sum-k0,相当于sumk属于一种情况12sum3 还有一种情况是 sum-xk,我们看到123sum6x3的时候sum-xk3我们也可以认为是满足情况的 就是除去最后一个数前面的区间 第二步算法原理 解法1暴力法时间复杂度为On^2 双循环求出所有子数组的和记录等于k的次数 解法2哈希表时间复杂度O(n)
首先思考暴力法的计算过程我们会发现暴力法中存在很多重复计算的过程。例如我们计算数组nums[0]nums[1]nums[2]时nums[1]nums[2]被算了一次当第二次循环计算nums[1]nums[2]的时候它又被计算了一次。所以如果想要减少算法的时间复杂度我们需要考虑如何减少重复计算。 因为数组的个数有限所以计算出所有的累加和时间为O(n),我们用一个HashMap记录sum[],其中key为sum[i]value为sum[i]出现的次数。若存在sum-kxx对应的value值为ret则代表这种情况下有ret个子数组和为k。依次累加x1、x2...最终求出总个数。
步骤就是我们拿[1,1,1]来做说明
sum1 sum-k!0 就不记入hash中然后我们将hash[sum]就将sum1存入hash表中sum112 sum-k0 记入hash中ret然后就将hash[sum] ,就将sum2存入hash中 sum1113 sum-k1 此时sum-k1在hash表中出现过ret然后就将hash[sum],将sum3存入hash表中
我们疑惑的是为什么sum-k1也ret因为我们上面说过了sum-k1,其实就是sum-1k,如果前面存在sum1的话剩下的区间区间和等于k。
假如说sum-k等于前面出现过的某个前缀和的话那么sum减去x其实就是减去了前面的一个区间此时剩下的这个区间的和就等于k。 当sum-k1的时候说明sum减去前缀和为1的区间剩下的区间的和等于k对应在这个111上就是sum减去第一个1之后剩下的区间加起来等于k。 也就是我上述说的俩种情况。第一种情况就是累加碰到sum[i]k的那么就满足第二种情况就是加到某个值之和之后我们减去k剩下的区间和是曾经累加的和那么我们就也ret。
这就得运用到hash表了记录每次sum的值。 第三步代码
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,inthash;//统计前缀和出现的次数hash[0]1; //下标为0存入1如果后面的sum-k0那么就加对应的值//hash[0]1 0,1绑定前面的0代表sum-k0后面的1代表次数int sum0,ret0;for(auto x:nums){sumx;//前缀和if(hash.count(sum-k)) rethash[sum-k];//统计个数//sum-k0或者sum-k曾经出现的前缀和_)hash[sum];//将当前的前缀和留在hash中}return ret;}
};
