目录
- 前言
- 算法题(LeetCode刷题209长度最小的子数组)—(保姆级别讲解)
-
- 结束语
前言
本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!!
算法题(LeetCode刷题209长度最小的子数组)—(保姆级别讲解)
力扣题目链接
分析题目
- 数组为
正整型
- 找出的子数组需要保证是
连续
的并且长度最小
算法思想(重要)
这里主要讲解两种算法思想,分别是:
- 暴力解法
- 滑动窗口
暴力解法代码:
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
int subLength = 0;
for (int i = 0; i < nums.size(); i++) {
sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
break;
}
}
}
return result == INT32_MAX ? 0 : result;
}
};
时间复杂度:O(n^2)
空间复杂度:O(1)
为了更能让大家了解暴力解法的算法思想,作者特意画了一张图供大家观看!!!
滑动窗口代码
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
int i = 0;
int subLength = 0;
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
while (sum >= s) {
subLength = (j - i + 1);
result = result < subLength ? result : subLength;
sum -= nums[i++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
为了更能让大家了解暴力解法的算法思想,作者特意画了一张图供大家观看!!!
结束语
如果觉得这篇文章还不错的话,记得点赞 ,支持下!!!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)