★ 算法OJ题 ★ 力扣209 - 长度最小的子数组

本文主要是介绍★ 算法OJ题 ★ 力扣209 - 长度最小的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Ciallo～(∠・ω< )⌒☆ ~ 今天，简将和大家一起做一道滑动窗口算法题--长度最小的子数组~

一题目

二算法解析

解法⼀：暴力求解

解法二：滑动窗口

三编写算法

一题目

209. 长度最小的子数组 - 力扣（LeetCode）

二算法解析

解法⼀：暴力求解

算法思路：从前往后枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个起始位置开始寻找⼀段最短的区间，使得这段区间的和大于等于目标值。将所有元素作为起始位置所得的结果中，找到最小值即可。（会超时）

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){// 记录结果int ret = INT_MAX;int n = nums.size();// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start = 0; start < n; start++){int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++){sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满⾜条件时{// 更新结果，start 开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};

此方法可以通过以下两个优化，成为解法二：

解法二：滑动窗口

滑动窗口的好处

利用单调性，使用“同向双指针”优化，规避了很多没有必要的枚举行为~

滑动窗口什么时候用呢？~

有单调性，有两个指针向同向移动且不回退时可以用~

滑动窗口怎么用呢？~

定义两个指针，left = 0, right = 0;
进窗口
判断（循环）
更新结果，出窗口

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次，任意一个指针到底就会结束。因此时间复杂度是 O(N) 。

三编写算法

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX, sum = 0;int n = nums.size();for (int left = 0, right = 0; right < n; right++){sum += nums[right]; // 进窗⼝while(sum >= target) // 判断{ret = min(ret, right - left + 1); // 更新结果sum -= nums[left]; left++;// 出窗⼝}}return ret == INT_MAX ? 0 : ret;}
};