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

Question

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]之后被忽略吗？

Answer 1

liuyubobobo 2017-08-19 08:31:56

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

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

• 提问者 tzkone3753223 #1

  谢谢老师的回复，你说的“这样一个sum一定产生自上一次循环”，我理解的是这样：之所以进入while循环后会跳过if语句进入else语句，说明进入while循环的sum是已经>=s，而这个已经>=s的sum是在这次进入while循环之前产生的，也就是您说的上一次循环产生的，这样该sum已经在上一次循环中处理了； 老师我这样理解对吗？

• liuyubobobo 回复 提问者 tzkone3753223 #2

  是的哦：）

• 提问者 tzkone3753223 回复 liuyubobobo #3

  嗯嗯，谢谢老师的答复。  老师，您每天都会来这里定时给我们解答问题么？

点开查看后面6条评论