合肥做网站优化哪家好,贵阳网站建设黔搜,学习网站建设多少钱,成都住建局官网保租房#x1f4bb;文章目录 #x1f4c4;题目✏️题目解析 思路#x1f4d3;总结 #x1f4c4;题目
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …,… 文章目录 题目✏️题目解析 思路总结 题目
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2 输入 target 4, nums [1,4,4] 输出 1 示例 3 输入 target 11, nums [1,1,1,1,1,1,1,1] 输出 0 提示 1 ≤ t a r g e t ≥ 1 0 9 1 \le target \ge 10^9 1≤target≥109 1 ≤ n u m s . l e n g t h ≥ 1 0 5 1 \le nums.length \ge 10^5 1≤nums.length≥105 1 ≤ n u m s [ i ] ≥ 1 0 5 1 \le nums[i] \ge 10^5 1≤nums[i]≥105
✏️题目解析 思路
题目要求我们在数组中寻找和为target的最小子数组我们可以先去想出暴力解法然后再推算出滑动窗口的解法。
暴力法 我们需要找到最短的连续数组那么最简单的方式就是用两个for循环去遍历数组累加数值只要数值 ≥ t a r g e t \ge target ≥target 就更新最小长度的状态。 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int ret INT_MAX;for(int left 0; left n; left){int sum 0;for(int right left; right n; right) {sum nums[right]; //累加数据if(sum target){ret min(ret, right - left 1); //更新状态break; //已经找到了最小的长度所以退出该层循环}}}return ret INT_MAX ? 0 : ret;}
};时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1)
滑动窗口
滑动窗口的题目大抵都有一个固定的划分过程
right进窗口判断 更新结果状态根据题目不同也可能在判断后更新状态出窗口(left)
我们从暴力法中不难发现其实当我们更新最小子数组长度时 l e f t 1 → r i g h t left1\to right left1→right 的这段区间是重复遍历的于是我们便可以使用滑动窗口来进行优化。当我们的 s u m ≥ t a r g e t sum \ge target sum≥target 时同时更新 l e f t left left 的位置 与 最小子数组的长度所谓的滑动窗口也是一种特殊的双指针类型只不过两个指针的指向都是相同的方向。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int sum 0, ret INT_MAX;for(int left 0, right 0; right n; right){sum nums[right]; //进窗口while(sum target) //判断{ret min(ret, right-left1); //更新状态sum - nums[left]; //出窗口}}return ret INT_MAX ? 0 : ret; //返回结果}
};时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
总结 博客主页主页 我的专栏C 我的githubgithub
