黄冈论坛网站有哪些,给wordpress首页添加公告栏,提升学历官网报名,微信怎么做链接网站文章目录长度最小的子数组习题暴力解法滑动窗口长度最小的子数组
本节对应代码随想录中#xff1a;代码随想录#xff0c;讲解视频#xff1a;拿下滑动窗口#xff01; | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili
习题
题目链接#xff1a;209. 长度最小的子数…
文章目录长度最小的子数组习题暴力解法滑动窗口长度最小的子数组
本节对应代码随想录中代码随想录讲解视频拿下滑动窗口 | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili
习题
题目链接209. 长度最小的子数组 - 力扣LeetCode
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。
暴力解法
直接能想到的就是用两个 for 循环第一个循环遍历起始位置第二个 for 循环向后遍历直到找到满足其和 ≥ target 的位置我的代码如下(非最优并且会超时仅用于个人分析记录)
class Solution {public:int minSubArrayLen(int target, vectorint nums) {int res 999999;for (int i 0; i nums.size(); i) {int sum 0, count 999999;for (int j i; j nums.size(); j) {sum nums[j];if (sum target) {count j - i 1;break;}}if (count res) {res count;}}if(res!999999){return res;}return 0;}
};比较代码随想录上的暴力解法有以下几点可以注意下
初始 res 时本意是想初始一个比较大的值用 resINT32_MAX 更好 INT_MAX 一般和 INT32_MAX 相同但如果是16位时 INT_MAX 要更小点所以用 INT32_MAX 更好 代码中后面两个 if 判断换成三元运算符更好即 ? :
滑动窗口
C中的滑动窗口是一种常见的数组/字符串问题的解决方案它可以将一个问题的时间复杂度从 O(n^2)降低到 O(n)或者 O(nlogn)通常涉及到从给定的数据序列中找到需要进行操作的子串或子序列等。
滑动窗口的基本思路是用两个指针表示现在关注的区间即左端点(left pointer)和右端点(right pointer)让其构成一个窗口。移动右指针扩大长度直到包含满足条件的子串比如大于等于target。然后尝试缩小左端点以尽可能的减小满足条件的窗口长度同时继续移动右指针查找再次满足条件的子串。重复这个过程直到最右侧得到最优解。
暴力解法中我们是遍历窗口的初始位置对于每个初始位置向后遍历剩余元素寻找满足条件的窗口。而滑动窗口是遍历窗口的结束位置如果当前窗口满足条件那左边的指针就要向右移动即缩小窗口其实也算是双指针。
class Solution {public:int minSubArrayLen(int target, vectorint nums) {int left 0, sum 0,subLength 0;int ans INT32_MAX; // 答案初始化为整数最大值for (int right 0; right nums.size(); right) {sum nums[right];while (sum target) { // 当sumtarget时意味着当前窗口的总值大于等于target了subLength (right - left 1); // 取子序列的长度ans ans subLength ? ans : subLength; // 更新anssum - nums[left]; // 窗口右移那就要减去原来窗口左边的值left; // 通过左指针向右移动收缩窗口}}return ans INT32_MAX ? 0 : ans; // 如果没找到就返回0}
};代码中 while (sum target) 使用的是 while 而不是 if因为当缩小窗口的时候是一个循环的过程。
如1 1 1 4中 target4那找到满足条件的窗口4的时候左指针应该是从初始的1不断向右移动直到新的窗口不大于等于 target 时停止
