leetcode209. 长度最小的子数组(暴力+滑动窗口)
2021/12/27 23:15:27
本文主要是介绍leetcode209. 长度最小的子数组(暴力+滑动窗口),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一:题目
二:暴力+滑动窗口
1:暴力解法
class Solution { public: int min (int a ,int b){ return a < b ? a : b; } int minSubArrayLen(int target, vector<int>& nums) { int minx = 100001; for(int i = 0; i < nums.size(); i++){ vector<int> v; int sum = nums[i]; v.push_back(nums[i]); for(int j = i + 1; j < nums.size(); j++){ if(sum < target){ sum += nums[j]; v.push_back(nums[j]); }else{ break;//当已经找到超过target的序列的时候 就可以跳出循环 } } if(sum >= target) minx = min(minx,v.size()); } if(minx == 100001) return 0; else return minx; } };
2:滑动窗口
(1):思路
思路:
1.滑动窗口方法,类似与双指针
2.先介绍滑动窗口的三要素
滑动窗口的起始位置,
窗口的范围大小
窗口的结束位置
3.在本题中,我们的起始位置是数组的开头,窗口的范围大小是我们累加的和,结束位置是我们的累加和大于target 的元素位置.
4.那么滑动窗口的精髓之处在于移动起始位置的指针,当我们统计到一个满足target的时候,我们将sum 剪去 nums[i++] (i是起始位置) ,那么就相当于我们向后移动一个元素
(2):上码
class Solution { public: int min (int a ,int b){ return a < b ? a : b; } int minSubArrayLen(int target, vector<int>& nums) { /** 思路:1.滑动窗口方法,类似与双指针 2.先介绍滑动窗口的三要素 滑动窗口的起始位置, 窗口的范围大小 窗口的结束位置 3.在本题中,我们的起始位置是数组的开头,窗口的范围大小是我们累加的和,结束位置是我们的累加和大于target 的元素位置. 4.那么滑动窗口的精髓之处在于移动起始位置的指针,当我们统计到一个满足target的时候,我们将sum 剪去 nums[i++] (i是起始位置) ,那么就相当于我们向后移动一个元素 **/ int minx = 100001; int arraylength = 0;//滑动窗口的长度 int sum = 0;//窗口的大小 int j = 0;//滑动窗口的起始 位置 for(int i = 0; i < nums.size(); i++) { sum += nums[i]; while(sum >= target){ arraylength = i - j + 1;//这个可以拿例子理解 minx = min(minx,arraylength); sum -= nums[j++];//这里体现滑动窗口的精髓之处 我们可以获知这里是移动出窗口的起始位置 } } return minx == 100001 ? 0 : minx; } };
不用猜 暴力解法 一定是菜鸡杰的解法 哈哈哈 菜鸡杰也只会暴力解决一切 但该学习学习还是得学 一看评论区 卧槽 还能这么做 我真菜 菜鸡杰果然是菜鸡 哈哈哈 加油 各位 !!
这篇关于leetcode209. 长度最小的子数组(暴力+滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升