做可动模型的网站,天津住建网,创建一个网站的费用,logo设计制作网站给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。
示例 1#xff1a;
输入…给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0
提示
1 target 1091 nums.length 1051 nums[i] 105
思路
暴力枚举除外想要找出连续并且相加大于target的最短的字串至少需要两个指针进行遍历一个在前一个在后。
第一个针对枚举次数的优化left指针定住right往右走每定义sum每次加等right大于traget后就可以停止遍历了因为要找最短right再往后只会找到更长的此时单趟遍历结束。 此时可以直接让left右移 sum-nums[left];再次比较此时子串和是否大于target因为有可能右移之后依然target,此时len还变短了如果不符合条件再开始下一趟遍历然后继续找符合要求的字串找到后和原本的len进行比较如果比原来的len小就更新比原来大就移动left然后重复上述操作。
此时可以发现left和right和通常意义下的双指针不同不是都向内移动而是同向进行移动此时这种方法就叫做同向双指针也叫做滑动窗口。 就像一个随时在变的窗口一样left是窗口左边right是窗口右边每次right移动可以比作进窗口left移动可以比作出窗口。总结一下就以下三步。 代码实现复杂度O(n)
虽然套了两次循环但时间复杂度可不是O(n^2),因为每次不管是left动还是right动整个窗口都是在向右移动不会再出现左移此时最差的情况也就是right一直走走到结尾然后left一直走走到结尾。
即便如此复杂度依然为2N.
while循环
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left0,right0,len0;int sum0;int len10;while(left(nums.size())){if(rightnums.size()) sumnums[right];//入窗口else{if(sumtarget) break;//如果right走到结尾此时sum依然小于target直接break因为窗口值只会越来越小}while(sumtarget)//判断大于target{len1right-left1;if(len0||len1len)//更新结果{lenlen1;}sum-nums[left];//出窗口}right;}return len;}
};
for循环
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left0,right0,len0;int sum0;int len10;for(int left0,right0;rightnums.size();right){sumnums[right];while(sumtarget){len1right-left1;if(len1len||len0){lenlen1;}sum-nums[left];}}return len;}
};
