链接
题目
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 子数组[numsl, numsl+1, ..., 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
思路1: 暴力解法。遍历枚举出所有的组合,然后判断。 时间复杂度为O(N!)。 显然是不可取的
思路2:滑动窗口思想。 用 left 和 right 指针维护一段窗口,并用sum记录该窗口中的数据的和。由于该题中数据都为正整数,那么当窗口中数据个数增多,那么该窗口内的数据之和也会增大。 当 窗口内数据之和<target时,right向后移动,使数据进入窗口。 当 窗口内数据之和>=target时,使left向后移动,从而使前面的数据出窗口。如下图。
为什么 当 窗口内数据之和>=target时,使left向后移动即可?
原因: 该题中数据都为 正整数,因此 当 窗口数据之和 >= target 时, 在left当前位置,right继续向后是毫无意义的,因为right向后移动,那么窗口之和会增加,仍旧是>=target的,但窗口长度会增大。题目要求是寻找符合>=target的最小子数组,即符合>=target且窗口长度最小的情况。因此 应该 以当前left位置的数据值得遍历的已经遍历完全了,left应该向后移动,来遍历下一个位置的情况。而left++后,right也无需回退,只需要更新sum的值,将退出窗口的数据的值减去,即可得到现在窗口的维护的数据的数据之和,即sum -= nums[原位置的left];
代码:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0 , right = 0;
int sum = 0;
int len = 0;
while(right < nums.size())
{
sum += nums[right];//更新 窗口的数据和
while(sum >= target)
{
//更新最短的子数组的长度len
if(len == 0) len = (right - left + 1);
else len = (right - left + 1) < len ? (right -left + 1) : len;
//更新sum
sum -= nums[left];
//出窗口
left++;
}
//进窗口
right++;
}
return len;
}
};
标签:right,窗口,target,nums,209,sum,数组,LeetCode,left
From: https://blog.csdn.net/2301_78913125/article/details/139890923