当前位置：首页 > news >正文

CC52.【C++ Cont】滑动窗口

news 2025/4/30 8:34:55

1.题目

2.分析

方法1:暴力枚举

方法2:暴力枚举的优化:"同向双指针",也称滑动窗口

前置知识

核心操作

例子解释

代码

提交结果

1.题目

LCR 008. 长度最小的子数组

给定一个含有 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 <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

注意：本题与主站 209 题相同：209. 长度最小的子数组 - 力扣（LeetCode）

2.分析

方法1:暴力枚举

第一层循环:枚举连续子数组的长度len,从1到nums.size()

第二层循环:对于每个len,可能有多个子数组,按子数组首元素的下标来枚举

第三层循环:计算子数组中元素的和,如果找到一个sum>=target,直接返回len

时间复杂度为 $O(N^3)$

以[2,3,1,2,4,3]为例分析:

len==1: [2],[3],[1],[2],[4],[3]

len==2: [2,3],[3,1],[1,2],[2,4],[4,3]

len==3: [2,3,1],[3,1,2],[1,2,4],[2,4,3]

len==4: [2,3,1,2],[3,1,2,4],[1,2,4,3]

len==5: [2,3,1,2,4],[3,1,2,4,3]

len==6: [2,3,1,2,4,3]

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {for (int len=1;len<=nums.size();len++){for (int i=0;i+len<=nums.size();i++){//计算子数组的和unsigned long long sum=0;for (int j=i;j<i+len;j++)sum+=nums[j];if (sum>=target)return len;}}return 0;}
};

提交结果:代码的时间复杂度为 $O(N^3)$ ,显然当数据量较大时会超时

方法2:暴力枚举的优化:"同向双指针",也称滑动窗口

前置知识

给定闭区间[left,right],left为区间左边界,right为区间的右边界

由于题目给出"给定一个含有 n 个正整数的数组",数组中元素都是正整数,则right变大时,区间的元素和也变大,则可以利用区间的元素和的单调性写"滑动窗口",这样就规避掉方法1没有必要的枚举行为

核心操作

将[left,right]之间连续的元素视为窗口

进窗口:right++,让新元素进入窗口

出窗口:left++,让旧元素离开窗口

例子解释

在遍历的同时去求和,类似前缀和思想,仍然以[2,3,1,2,4,3],target = 7为例说明:

设len存储返回值,left给出左边界,将left固定,right从左边界向后枚举,right每指向一个新数,就为sum加上这个新数(思想类似前缀和,比方法1每次循环重新计算一遍sum要快)

一开始各个变量的初始值:

int left=0;
int right=0;
int sum=nums[0];
int len=10001;

注:len初始化为10001的原因:题目"1 <= nums.length <= 10^5",len设置成比nums.length稍大的数就行了

(红色区域为滑动窗口)

如果sum<target,right++,为"进窗口"(新数据进入窗口),同时sum加上对应的值

if (sum<target)
{right++;if (right==nums.size())break;sum+=nums[right];
}

此时sum>target,记录len的值:right-left+1==4,但这个len不一定是最小值,因此要继续"滑动"窗口

注意:此时没有必要继续right++,因为sum已经大于target,题目要求最小值

left++,为"出窗口"(移除旧数据)sum减去对应的值,注意right不用回退,要利用区间的元素和的单调性

if (sum>=target)
{len=min(len,right-left+1);sum-=nums[left];left++;
}

sum<target,"进窗口"

sum>target,窗口长度为4,取len=min(len,right-left+1),之后"出窗口"

sum>target,窗口长度为3,取len=min(len,right-left+1),之后"出窗口"

sum<target,"进窗口"

sum>target,窗口长度为3,取len=min(len,right-left+1),之后"出窗口"

sum==target,窗口长度为2,取len=min(len,right-left+1),之后"出窗口"

sum<target,但right已经到头了,因此结束循环,返回len,则可得出循环的框架:

while (right<nums.size())
{//do_something
}

"同向双指针":left和right向同一个方向移动

时间复杂度:right最多移动到nums.size()-1处,时间复杂度为 $O(N)$

代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0;int right=0;int sum=nums[0];int len=10001;while (right<nums.size()){if (sum<target){right++;if (right==nums.size())break;sum+=nums[right];}else//sum>=target{len=min(len,right-left+1);sum-=nums[left];left++;}}if (len==10001)return 0;elsereturn len;}
};