題目
題目鏈接：https://leetcode.cn/problems/minimum-size-subarray-sum/
給定一個含有 n個正整數的數組和一個正整數 target** 。**
找出該數組中滿足其總和大于等于target的長度最小的 子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度**。**如果不存在符合條件的子數組，返回 0 。
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組?[4,3]?是該條件下的長度最小的子數組。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {}
};
思路 & 代碼
暴力解法
#include <vector>
#include <cstdint>
#include <iostream>
using namespace std;class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0;int subLength = 0;int result = INT32_MAX;// 需要<cstdint>頭文件for(int i = 0; i < nums.size(); i++){sum = 0; // 是子序列的和，設置為0，用于下一個子序列的初始值for(int j = i; j < nums.size(); j++) {sum += nums[j];if (sum >= target){subLength = j - i + 1;result = result > subLength ? subLength : result;break; // 找到符合條件的子序列，就退出當前的 j 的for 循環。}}}if(result == INT32_MAX)return 0; // 說明沒有符合條件的子序列else return result;}
};
// @lc code=endint main() {Solution obj;vector<int> vec = {2,1,1,2,4,3};int target = 7;int res = obj.minSubArrayLen(target, vec);cout << res << endl;
}
時間復雜度：O(n^2)
空間復雜度：O(1)
滑動窗口
滑動窗口：不斷的調節子序列的起始位置和終止位置，從而得到想要的結果。
將暴力法中的兩個for循環改成使用一個for循環實現搜索。
- 窗口內是什么？
- 滿足其和 >= s 的長度最小的 連續 子數組
- 如何移動窗口的起始位置？
- 當前窗口的值 >= s，就要往前移動了
- 如何移動窗口的結束位置？
- 窗口的結束位置就是遍歷數組的指針，也就是for循環里的索引
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0;int subLength = 0;int result = INT32_MAX;// 需要<cstdint>頭文件int i = 0;for(int j = 0; j < nums.size(); j++) {sum += nums[j];while (sum >= target){subLength = j - i + 1;result = result > subLength ? subLength : result;sum -= nums[i];i++;}}if(result == INT32_MAX)return 0; // 說明沒有符合條件的子序列else return result;}
};
時間復雜度：O(n)
空間復雜度：O(1)
每個元素在滑動窗后進來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復雜度是 2 × n 也就是O(n)
)
)
