[M双指针] lc209. 长度最小的子数组(双指针+好题)
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接：209. 长度最小的子数组
题单：
-
- 滑动窗口（定长/不定长/多指针）
- 不定长滑动窗口（求最长/最大）
2. 题目解析
思路：
- 朴素双指针即可。
- r 向右拓展时，判断 l 是否可以向右拓展，在满足题目要求的情况下获取到更短的子数组长度。
坑点：
- 如果做了前几个题目的话，可能在计算答案的时候不会去写这个 if 判断。
- 这样就会导致遇见第一个数，就将长度 1 取了 min 给到了 res，然后后续都不会再发生变化。
- 但这个第一个数，可能根本都不够 targe，这就是个错误的答案计数。
所以，针对问题，还需要具体分析。
- 时间复杂度： O ( 1 ) O(1) O(1)
- 空间复杂度： O ( 1 ) O(1) O(1)
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int res = 1e9, cur = 0;for (int l = 0, r = 0; r < n; r ++ ) {cur += nums[r];while (l <= r && cur - nums[l] >= target) cur -= nums[l ++ ];// 这里需要注意下，它需要作为条件判断加上// 可能类似：3、713 都不需要将其作为判断条件。// 因为一开始的几个还没够，target，并且这里还取得是 min，就会导致数组长度很短，过不了用例...// 其他的要么是方案数、要么是最大，不受这个 min 的影响if (cur >= target) res = min(res, r - l + 1); }return res == 1e9 ? 0 : res;}
};