专题二：C++算法学习——滑动窗口_长度最小的子数组、

题目一：滑动窗口_长度最小的子数组

一、题目

2.算法原理

解法一：暴力枚举所有子数组之和O（n的三次方）

在sum的基础上加O(n的二次方 )

解法二：利用单调性，使用“同向双指针”来优化

同向双指针(滑动窗口)

怎么用？

更新结果不一样的题位置不一样

让right先找到最佳位置大于t

开始滑动，

正确性：虽然没有全部枚举，但利用单调性避免了很多没必要的美枚举行为

left不变，right不需要往后挪了，没必要

时间复杂度2n O(n)

3.代码

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(), sum = 0, minLen = INT_MAX; for (int left = 0, right = 0; right < n; right++) { sum += nums[right]; // 右窗口扩，加入当前数字 while (sum >= target) // 窗口和满足条件，尝试收缩左边界 { minLen = min(minLen, right - left + 1); // 更新最小长度 sum -= nums[left++]; // 左窗口缩，移出数字 } } return ret； };