一、題目
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 邪驮。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度处窥。如果不存在符合條件的子數(shù)組锭弊，返回 0 填硕。
二、示例
2.1> 示例 1：
【輸入】target = 7, nums = [2,3,1,2,4,3]
【輸出】2
【解釋】子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組炼吴。
2.2> 示例 2：
【輸入】target = 4, nums = [1,4,4]
【輸出】1
2.3> 示例 3：
【輸入】target = 11, nums = [1,1,1,1,1,1,1,1]
【輸出】0
提示：
-
1<= target <=10^9 -
1<= nums.length <=10^5 -
1<= nums[i] <=10^5
三本鸣、解題思路
根據(jù)題目描述我們要找出該數(shù)組中滿足其和大于等于target的長度最小的連續(xù)子數(shù)組。那么對于“連續(xù)子數(shù)組”這個(gè)關(guān)鍵點(diǎn)硅蹦，我們很容易就會想到能否采用滑動窗口來解決這道題荣德。
而題目中的另一個(gè)關(guān)鍵點(diǎn)——連續(xù)子數(shù)組其和需要大于等于target闷煤，那么就可以理解為變化窗口大小的依據(jù)了，具體規(guī)則如下所示：
【規(guī)則1】如果連續(xù)子數(shù)組其和 大于等于
target涮瞻，則擴(kuò)大窗口的右側(cè)部分鲤拿；
【規(guī)則2】如果連續(xù)子數(shù)組其和 小于target，則縮小窗口的左側(cè)部分署咽；
隨著遍歷結(jié)束近顷，我們返回滿足上述條件中最小長度即可；在解題過程中宁否，我們可以采用雙指針的方式來模擬滑動窗口窒升。那么以上就是本題的解題思路了，為了便于大家理解慕匠，我們一下以輸入 target = 7, nums = [2,3,1,2,4,3]為例异剥，看一下具體的操作流程是怎么樣的。具體請見下圖所示：
四絮重、代碼實(shí)現(xiàn)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0, j = 0, sum = nums[0], result = 100001;
while(true) {
if (sum < target) {
if (j >= nums.length - 1) break;
sum += nums[++j]; // 向右移動右指針
} else {
result = Math.min(result, j - i + 1);
sum -= nums[i++]; // 向右移動左指針
}
}
return result == 100001 ? 0 : result;
}
}
今天的文章內(nèi)容就這些了：
寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章歹苦，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 青伤。
更多技術(shù)干貨，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ \(o)/ ~ 「干貨分享殴瘦，每天更新」
