leetcode -- 209 长度最小的子数组[滑动窗口/c++]

2023-12-13 18:00:56

原题链接:209. 长度最小的子数组 - 力扣(LeetCode)

算法原理:

滑动窗口其实就是同向双指针,因为计算结果的单调性,在符合条件的情况下,左右指针不必往回回溯,而实现优化的效果。

滑动窗口分为4步(构成一个循环)

1. 进窗口(对right指针指向的数据进行处理)

2.判断(判断的作用是决定是否要进行出窗口操作)

3.出窗口(一般是移动left指针)

4.更新状态(可能在出窗口前,也可能在出窗口后,依情况而定)

这里的进出窗口针对的是数组中的元素,比如right++后指向的元素,就表示被放进了窗口。

为什么滑动窗口不会漏解?

理由一开始就说了,根据计算结果的单调性,省略掉的结果不影响最终值。

比如此题中,滑动窗口(双指针包围的数)内的数值和已经大于或等于目标值,此时right再++的话,len长度就更长了,题目要求返回长度最小的子数组长度,所以没有再让right++的必要,直接让left++,开始遍历下一个子数组。

注意,left++时,right不必重新回到left位置,只要让sum减去原本的left指向的值即可。因为我们是在一达到题目要求(大于等于目标值)的情况下就进行调整的,也就是出窗口操作,所以也不可能存在漏解的情况。

代码

此题更新状态需要用到left和right指针的相对位置,所以是在出窗口之前更新状态

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX,n = nums.size(),sum =0;
for(int left =0,right = 0;right<n;right++)
{
    //进窗口
    sum += nums[right];
    //判断
    while(sum >= target)
    {
        len = min(len,right-left+1); //更新状态
        sum-=nums[left++];//出窗口
    }
}
return len == INT_MAX?0:len;
    }
};

文章来源:https://blog.csdn.net/lrsnt/article/details/134975828
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。