关于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就加;富裕了就减),然后看根据当前窗口是否能够得到一个解。富裕了就减这种情况,一定在上一次调整窗口发现富裕了以后,已经进行记录了:)
092017-08-19
相似问题