LeetCode209 长度最小的子数组
前言
题目: 209.长度最小的子数组
文档: 代码随想录——长度最小的子数组
编程语言: C++
解题状态: 没有思路,暴力解法都没思路…
思路
注意,子数组指的是连续子数组,不然本题就没有意义了。
代码
方法一: 暴力解法
所谓暴力解题,也要将时间复杂度控制在两个循环以内。
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public:
int minSubArrayLen(int target, 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 = sum + nums[j];
if (sum >= target) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
}
}
}
if (result == INT32_MAX) result = 0;
return result;
}
};
方法二: 滑动窗口
所谓滑动窗口就是不断调节子数组的起始位置和终止位置,以得到我们想要的结果。
滑动窗口需要确定以下几点:
- 窗口内的元素是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的终止位置?
本题的关键在于根据当前子数组内的元素和,不断调整窗口的起始位置,降低时间复杂度。
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口内元素的和
int i = 0; // 滑动窗口的起点
int subLen = 0; // 子数组的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
while (sum >= target) {
subLen = j - i + 1;
result = result < subLen ? result : subLen;
sum -= nums[i++];
}
}
if (result == INT32_MAX) result = 0;
return result;
}
};
原文地址:https://blog.csdn.net/daishabby2486/article/details/140664110
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!