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

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

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中：

1 2 3 4 5 6 7 8 9 10

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条评论