sum比target小就进窗口,sum比target大就出窗口,由于数组是正数,所以相加会使sum变大,相减会使sum变小,至于为什么可以这样做,这其实是在暴力枚举的基础上进行了优化,例如2,3,1,2相加等于8已经超过target,这样就不需要继续加后面的4,3,因为此时已经满足条件,我们要做的是在满足要求的基础上使len尽量小。
代码实现如下:
class Solution {
public:
int minSubArrayLen(int target, vector& nums) {
int sum = 0, len = INT_MAX, n = nums.size();
for (int right = 0, left = 0; right < n; right++)
{
sum += nums[right]; // 进窗口
while (sum >= target) // 判断
{
len = min(len, right - left + 1); // 更新结果
sum -= nums[left++]; // 出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};