209.長(zhǎng)度最小的子數(shù)組
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 肆汹。
找出該數(shù)組中滿足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] 终吼，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組油宜，返回 0 。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組屑彻。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
進(jìn)階：
- 如果你已經(jīng)實(shí)現(xiàn)
O(n)時(shí)間復(fù)雜度的解法, 請(qǐng)嘗試設(shè)計(jì)一個(gè)O(n log(n))時(shí)間復(fù)雜度的解法验庙。
209. 長(zhǎng)度最小的子數(shù)組 - 力扣（LeetCode）
思路：
要尋找符合條件的最小子數(shù)組，自然而然就可以想到通過把所有的子數(shù)組遍歷一遍社牲，找到符合要求的粪薛，再比較其中的長(zhǎng)度最小的子數(shù)組。這樣的話搏恤，要使用兩層for循環(huán)违寿，屬于暴力解法，時(shí)間復(fù)雜度較高熟空。
做這道題我們可以使用滑動(dòng)窗口的方法藤巢，其實(shí)和雙指針法是比較類似的。只不過移動(dòng)的是整個(gè)一個(gè)區(qū)間息罗，所以稱為滑動(dòng)窗口掂咒。
暴力解法：
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX; // 讓result等于一個(gè)極大的值，INT32_MAX為宏定義
int sum = 0; // 存儲(chǔ)子序列的數(shù)值之和
int subLength = 0; // 存儲(chǔ)子序列的長(zhǎng)度
for (int i = 0; i < nums.size(); i++) { // 設(shè)置子序列起點(diǎn)為i
sum = 0;
for (int j = i; j < nums.size(); j++) { // 設(shè)置子序列終止位置為j
sum += nums[j];
if (sum >= s) { // 一旦發(fā)現(xiàn)子序列和超過了s，更新result
subLength = j - i + 1; // 取子序列的長(zhǎng)度
result = result < subLength ? result : subLength; //比較更新result
break; //找到符合條件最短的子序列绍刮，退出循環(huán)
}
}
// 如果result沒有被賦值的話温圆，就返回0，說明沒有符合條件的子序列
return result == INT32_MAX ? 0 : result;
}
}
};
時(shí)間復(fù)雜度：O(n^2)
滑動(dòng)窗口法：
我們可以使用滑動(dòng)窗口法對(duì)時(shí)間復(fù)雜度進(jìn)行優(yōu)化孩革，不斷調(diào)節(jié)子序列的起始和終止位置岁歉。
設(shè)定兩個(gè)指針i和j，分別指向滑動(dòng)窗口的起始位置以及終止位置膝蜈。
這里我們就需要考慮滑動(dòng)窗口外層for循環(huán)中遍歷的應(yīng)該是窗口的起始位置還是終止位置锅移。
如果起始位置一直在移動(dòng)的話，不可避免的饱搏，我們?cè)谄鹗嘉恢妹看巫兓胺翘辏K止位置都需要對(duì)整條數(shù)組進(jìn)行一遍遍歷，若是這么做窍帝，那就與之前的暴力解法無異了努潘。
所以我們采用循環(huán)的索引表示滑動(dòng)窗口終止位置的方法，讓j先去不斷移動(dòng)坤学，用sum記錄此時(shí)窗口中的和疯坤，一旦sum的值大于等于目標(biāo)值，我們就可以對(duì)起始位置進(jìn)行更新深浮，縮小起始位置压怠，從而判斷是否存在更小長(zhǎng)度，符合條件的子數(shù)組飞苇。
class Solution {
public:
//滑動(dòng)窗口
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX; //讓result取一個(gè)極大值
int sum = 0; // 滑動(dòng)窗口數(shù)值之和
int i = 0; // 滑動(dòng)窗口起始位置
int subLength = 0; // 滑動(dòng)窗口的長(zhǎng)度
for (int j = 0; j < nums.size(); j++) { //j指向滑動(dòng)窗口的末尾位置菌瘫，用來遍歷
sum += nums[j];
// 注意這里使用while，每次更新 i（起始位置）布卡，并不斷比較子序列是否符合條件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的長(zhǎng)度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 不斷變更i（子序列的起始位置）
}
}
// 如果result沒有被賦值的話雨让，就返回0，說明沒有符合條件的子序列
return result == INT32_MAX ? 0 : result;
}
};
時(shí)間復(fù)雜度：O（2n) 可以視作 O（n)
二分查找法：
這種方法利用了之前所學(xué)到的二分查找法忿等，先創(chuàng)建一個(gè)數(shù)組sums用于存儲(chǔ)數(shù)組nums的前綴和栖忠。sums[i]表示nums[0]到nums[i-1]的元素和。
得到前綴和后贸街，對(duì)于每個(gè)開始下標(biāo)i庵寞，通過二分查找得到大于等于i的最小下標(biāo)bound，使得sums[bound]-sums[i-1]大于等于s薛匪。并實(shí)時(shí)更新子數(shù)組的最小長(zhǎng)度bound-(i-1)
這里使用二分查找的前提是前綴和數(shù)組sums是有序的捐川，由于原數(shù)組中都是正整數(shù)，所以所得到的的前綴和數(shù)組也必定是遞增的逸尖，所以我們可以使用二分查找的方法古沥。
class Solution {
public:
//二分查找
int minSubArrayLen3(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) { //判斷數(shù)組為空的情況
return 0;
}
int ans = INT_MAX; //先將結(jié)果值設(shè)置為一個(gè)極大值
vector<int> sums(n + 1, 0);
// 為了方便計(jì)算瘸右，令 size = n + 1
// sums[0] = 0 意味著前 0 個(gè)元素的前綴和為 0
// sums[1] = A[0] 前 1 個(gè)元素的前綴和為 A[0]
// 以此類推
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= n; i++) {
int target = s + sums[i - 1];
auto bound = lower_bound(sums.begin(), sums.end(), target); //使用現(xiàn)成的庫函數(shù)來實(shí)現(xiàn)這里二分查找大于等于某個(gè)數(shù)的第一個(gè)位置的功能
if (bound != sums.end()) {
ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
}
}
return ans == INT_MAX ? 0 : ans;
}
};
時(shí)間復(fù)雜度：O(nlogn)
后續(xù)也會(huì)堅(jiān)持更新我的LeetCode刷題筆記，歡迎大家關(guān)注我渐白，一起學(xué)習(xí)尊浓。
如果這篇文章對(duì)你有幫助逞频，或者你喜歡這篇題解纯衍，可以給我點(diǎn)個(gè)贊哦。
CSDN同步更新苗胀，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主
往期回顧：
LeetCode977.有序數(shù)組的平方
LeetCode844.比較含退格的字符串
LeetCode283.移動(dòng)零
LeetCode27.移除元素
LeetCode26.刪除有序數(shù)組中的重復(fù)項(xiàng)
