給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 闭专。
找出該數(shù)組中滿足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長(zhǎng)度慎宾。如果不存在符合條件的子數(shù)組舌菜，返回 0 慢味。
● 進(jìn)階：如果你已經(jīng)實(shí)現(xiàn) O(n) 時(shí)間復(fù)雜度的解法, 請(qǐng)嘗試設(shè)計(jì)一個(gè) O(n log(n)) 時(shí)間復(fù)雜度的解法。
解題思路：
● 方式一：滑動(dòng)窗口盔几。 時(shí)間復(fù)雜度：O(n)
設(shè)立指針i晴弃，j，初始化下標(biāo)均為0逊拍。j 不斷后移上鞠，并且計(jì)算當(dāng)前窗口的和sum，直到sum ≥ target芯丧。此時(shí)后移i指針芍阎，并更新sum，直到無(wú)法再移動(dòng) i 缨恒。重復(fù)上述步驟谴咸，直到 j 完成遍歷轮听。在此過(guò)程中記錄滑動(dòng)窗口的最小值。
● 方式二：數(shù)組前綴和 + 二分查找 時(shí)間復(fù)雜度：O(nlogn)
由于該數(shù)組是一個(gè)正整數(shù)數(shù)組岭佳，計(jì)算出來(lái)的前綴和數(shù)組sums一定是一個(gè)遞增數(shù)組血巍，滿足二分條件。
??定義sums[i] = nums[1] + nums[2] + …… + nums[i];
??則sums[n] - sums[m] = nums[m+1] + nums[m+2] + …… + nums[n].（此時(shí)不包含nums[m]）
問(wèn)題需求：sums[n] - sums[m] >= target珊随，等價(jià)于sums[m] + target <= sums[n]述寡。
此時(shí)問(wèn)題可以轉(zhuǎn)換為，當(dāng)固定開(kāi)始下標(biāo)為m+1時(shí)叶洞，target(新) = sums[m] + target(舊)鲫凶，在遞增數(shù)組sums中找到第一個(gè)≥target(新)的元素下標(biāo)。
（）
（）
舉例：
sums[0] + target(舊) → 找到從下標(biāo)1開(kāi)始的滿足題意的最小長(zhǎng)度
sums[1] + target(舊) → 找到從下標(biāo)2開(kāi)始的滿足題意的最小長(zhǎng)度
……
sums[n-2] + target(舊) → 找到從下標(biāo)n-1開(kāi)始的滿足題意的最小長(zhǎng)度（n為數(shù)組長(zhǎng)度）
?【sums[n-1]也要被計(jì)算财饥，因?yàn)殡m然sums[n-1]不作為開(kāi)始下標(biāo)，但是可以作為結(jié)束下標(biāo)折晦，從另一個(gè)角度說(shuō)钥星，需要把全部元素的和計(jì)算一遍】
? 對(duì)上述結(jié)果觀察，可以發(fā)現(xiàn)nums[0]沒(méi)有被包括進(jìn)來(lái)满着，所以我們要重新修改sums的定義谦炒。
??定義sums[i] = nums[1] + nums[2] + …… + nums[i-1];
??則sums[n] - sums[m] = nums[m] + nums[m+1] + …… + nums[n].（此時(shí)包含nums[m]）
問(wèn)題需求【不變】：sums[n] - sums[m] >= target，等價(jià)于sums[m] + target <= sums[n]风喇。
此時(shí)問(wèn)題可以轉(zhuǎn)換為宁改，當(dāng)固定開(kāi)始下標(biāo)為【m】時(shí)，target(新) = sums[m] + target(舊)魂莫，在遞增數(shù)組sums中找到第一個(gè)≥target(新)的元素下標(biāo)还蹲。
舉例：
sums[0] + target(舊) → 找到從下標(biāo)0開(kāi)始的滿足題意的最小長(zhǎng)度
sums[1] + target(舊) → 找到從下標(biāo)1開(kāi)始的滿足題意的最小長(zhǎng)度
……
sums[n-1] + target(舊) → 找到從下標(biāo)n-1開(kāi)始的滿足題意的最小長(zhǎng)度（n為數(shù)組長(zhǎng)度）
?【sums[n]也要被計(jì)算，因?yàn)殡m然sums[n-1]不作為開(kāi)始下標(biāo)耙考，但是可以作為結(jié)束下標(biāo)谜喊，從另一個(gè)角度說(shuō)，需要把全部元素的和計(jì)算一遍】倦始！
因此斗遏，通過(guò)遍歷每一個(gè)sums元素【為了固定開(kāi)始下標(biāo)】，調(diào)用二分查找鞋邑，并在此過(guò)程中記錄最小的長(zhǎng)度诵次，即可完成所求账蓉。
Java
● 方式一
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0;
int j = 0;
int sum = 0;
int result = nums.length;
while(j < nums.length){
sum += nums[j];
if(sum >= target){
// 嘗試移動(dòng)i指針
int tmp = (sum-nums[i]);
while(tmp >= target){
sum = tmp;
i++;
tmp = (sum-nums[i]);
}
tmp = j - i + 1;
if(result > tmp) result = tmp;
}
j++;
}
if(sum < target) return 0;
else return result;
}
}
● 方式二
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum[] = new int[nums.length + 1];
sum[0] = 0; // 包括nums[0]
for(int i=1; i<sum.length; i++){
sum[i] = sum[i - 1] + nums[i - 1];
}
int result = Integer.MAX_VALUE;
// 開(kāi)始固定開(kāi)始下標(biāo)
for(int i=0; i<nums.length; i++){
int newTarget = target + sum[i];
// 二分查找sums遞增數(shù)組：找到第一個(gè)比newTarget大的元素下標(biāo)
int l = i;
int r = sum.length - 1;
int mid = l + (r - l) / 2;
while(l <= r){
mid = l + (r - l) / 2;
if(sum[mid] < newTarget){
l = mid + 1;
}else{ // sum[mid] >= newTarget
r = mid - 1; // 保證下標(biāo)為l的是正確的
}
}
if(l >= sum.length) continue; // 說(shuō)明找不到
int curLen = l - i; // sum[t] 不包括 num[t]
if(result > curLen) result = curLen;
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
