关于Leetcode 209题应用滑动窗口解题的一个小问题?

来源:3-7 滑动窗口 Minimum Size Subarray Sum

tzkone3753223

2017-08-18

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.size() <= 0)
            return 0;
        
        int left = 0;//[left....right]为滑动窗口,初始时,没有一个元素
        int right = -1;
        
        int sum = 0; //初始化和sum为0
        int res = nums.size() + 1;//初始化一个最大长度
        
        while(left < nums.size()){
            
            if(right + 1 < nums.size() && sum < s)
                sum += nums[++right]; //加上right后面一个数值,然后跳到下面一个if语句
            else //sum>=s
                sum -= nums[left++]; //减去前一个
            
            if(sum >= s)
                res = min(res, right - left + 1);
        }
        
        if(res == nums.size() + 1)
            return 0;
        
        return res;
    }
};

以上是被Leetcode AC的答案,但是对其中有一个细节有点疑惑,该问题出现在while循环中if...else语句中的else

while(left < nums.size()){
            
            if(right + 1 < nums.size() && sum < s)
                sum += nums[++right]; //加上right后面一个数值,然后跳到下面一个if语句
            else //sum>=s
                sum -= nums[left++]; //减去前一个
            
            if(sum >= s)
                res = min(res, right - left + 1);
        }

else语句表示r达到尾部了,或者sum>=s,如果是后者,即sum>=s时,那么sum减去一个nums[left]之后再++,然后跳到后一个if语句,如果sum减去一个nums[left]之后的sum的值<s了,后面的if语句即不成立,那么在未减去nums[left]之前的这种情况不是被忽略了吗? 即刚进入else语句,且满足sum>=s这种情况不是会在减去一个nums[left]之后被忽略吗?

写回答

1回答

liuyubobobo

2017-08-19

如果sum >= s,再减去nums[left]后确实会被这次的第8行if忽略,但是这样的yigesum,一定产生自上次循环里,所以一定在上次循环已经处理过了:)


总体来说,我们的算法就是从一个空窗口开始,每次都调整窗口大小(不够s就加;富裕了就减),然后看根据当前窗口是否能够得到一个解。富裕了就减这种情况,一定在上一次调整窗口发现富裕了以后,已经进行记录了:)

0
9
tzkone3753223
回复
liuyubobobo
好的,谢谢老师那么及时的答复。 ^-^
2017-08-19
共9条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程