題目描述
leetcode 第209題：長度最小的子數組
給定一個含有 n 個正整數的數組和一個正整數 target 蝉娜。
找出該數組中滿足其和 ≥ target 的長度最小的 連續(xù)子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度底扳。如果不存在符合條件的子數組刃泌，返回 0 溯壶。
示例：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。
解題方法
滑動窗口
參照題解
- 解題思路
定義n存儲數組nums的長度
定義左右指針left和right，初始都為0
定義sumN統(tǒng)計每組子數組的和戚哎，初始為0
為求得最小子數組的長度minl，先賦值一個比n要大的數n+1
當right<n時嫂用，將right對應數值累加到sumN型凳，并右移right
當sumN>=正整數target時，計算此時子數組的長度嘱函，與minl相比取最小值
然后將left對應數值從sumN中減去甘畅，并右移left
若最終得到的minl與初始值相等，說明不存在符合條件的子數組往弓，返回0
反之疏唾，返回minl
- 復雜度
時間復雜度：O(n)，n是數組的長度
空間復雜度：O(1)
- 代碼實現(xiàn)
python3
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left = right = sumN = 0
minl = n+1
while right<n:
sumN += nums[right]
right += 1
while sumN>=target:
minl = min(minl,right-left)
sumN -= nums[left]
left += 1
return 0 if minl==n+1 else minl
php
class Solution {
function minSubArrayLen($target, $nums) {
$n = count($nums);
$left = $right = $sumN = 0;
$minl = $n+1;
while($right<$n){
$sumN += $nums[$right];
while($sumN>=$target){
$minl = min($minl,$right-$left+1);
$sumN -= $nums[$left];
$left++;
}
$right++;
}
if($minl==$n+1){
return 0;
}else{
return $minl;
}
}
}
- 文字草稿
target = 7
nums = [2,3,1,2,4,3]
第1組連續(xù)子數組和為2=2函似，out
第2組連續(xù)子數組和為5=2+3槐脏，out
第3組連續(xù)子數組和為6=2+3+1，out
第4組連續(xù)子數組和為8=2+3+1+2缴淋，長度為4
第5組連續(xù)子數組和為10=3+1+2+4准给，長度為4
第6組連續(xù)子數組和為10=1+2+4+3，長度為4
第7組連續(xù)子數組和為9=2+4+3重抖，長度為3
第8組連續(xù)子數組和為7=4+3露氮，長度為2
最小子數組的長度為2
