[209. Minimum Size Subarray Sum]
[(https://leetcode.cn/problems/minimum-size-subarray-sum/)
暴力解法
- 兩個for回圈，不斷尋找符合條件的子序列
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX; // 最終的結果
int total = 0; // 子序列的數值之和
int count = 0; // 子序列的長度
for (int i = 0; i < nums.size(); i++) { // 設定子序列起點為i
total = 0;
for (int j = i; j < nums.size(); j++) { // 設定子序列終止位置為j
total += nums[j];
if (total >= target) { // 一旦發現子序列和超過了s，更新result
count = j - i + 1; // 更新子序列的長度
result = result < subLength ? result : subLength;
break; // 因為是找符合條件最短的子序列，所以一旦符合條件就break
}
}
}
// 回傳0，說明沒有符合條件的子序列
return result == INT32_MAX ? 0 : result;
}
};
-
時間復雜度：O(n^2)
空間復雜度：O(1)
滑動視窗
- 所謂滑動視窗：不斷調節子序列起始位置和終止位置，從而得出想要的結果，
- 在暴力解法中，我們使用了兩個for回圈，若用滑動視窗如何以一個for回圈得出結果呢？
- 思路：
- 首先，一個for回圈是用來表示滑動視窗的起始位置，還是終止位置？若是表示起始位置，其實看著和暴力解法相差無幾，因此for回圈應該用來表示終止位置
- 三個重點：
- 滑動視窗內表示的是什么？
- 視窗其實就是一個滿足條件的連續子陣列
- 滑動視窗如何移動起始位置？
- 若視窗內總值sum大于target，則需要向前移動起始位置
- 滑動視窗如何移動終止位置？
- 若視窗內sum小于target，則需要向前移動終止位置
- 滑動視窗內表示的是什么？
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0; //滑動視窗起始位置
int total = 0; //滑動視窗終止位置
int count = 0; //滑動視窗長度
int result = INT32_MAX; //最終長度值
for( int right = 0; right < nums.size(); ) //for回圈控制終止位置
{
total += nums[right++];
++count;
//滑動視窗精髓
while(total >= target)
{
result = count < result ? count : result;
--count;
total -= nums[left++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
-
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513682.html
標籤：其他
上一篇：P6560 [SBCOI2020] 時光的流逝（DAG圖上博弈模板）
下一篇：代碼隨想錄 | 二叉樹