在做题中学习(43):长度最小的子数组

2024-01-07 19:31:26

LCR 008. 长度最小的子数组 - 力扣(LeetCode)

解法:同向双指针-------滑动窗口算法

解释:本是暴力枚举做法,因为全部是正整数,就可以利用单调性和双指针解决问题来节省时间

思路:

如上面图,right指针走到此处,sum > 7,长度为4,因为都是正整数,right再向后走仍然会 > 7,len也会变大,而题目要求符合条件最小的len,因此此时right不必动了,让left向后走,sum会缩小,因此让right又得向后走,直到走完整个数组,最后的len就是最小的子数组长度。

滑动窗口就是因为left? right 最后都会向后走,俩指针之间的部分(窗口)一直在滑动,因此同向双指针也叫滑动窗口算法。

所以总结下来步骤为:

1.left = 0, right = 0

2.进窗口

3.判断

4.出窗口

细节:len定义时不要为0,因为后续len重新赋值是要在原先和现在的值中选更小值。最后的len需要判断,因为若是遍历完数组一遍,len都没有变化,那就需要返回0.

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

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