文章目錄
- 1.題目要求
- 2.解題代碼
1.題目要求
給定一個含有 n 個正整數的數組和一個正整數 s ,找出該數組中滿足其和 ≥ s 的長度最小的連續子數組,并返回其長度。如果不存在符合條件的連續子數組,返回 0。
示例:
輸入:s = 7, nums = [2,3,1,2,4,3]
輸出:2
解釋:子數組 [4,3] 是該條件下的長度最小的連續子數組。
2.解題代碼
定義兩個指針 start 和 end 分別表示子數組的開始位置和結束位置,維護變量sum 存儲子數組中的元素和(即從 nums[start] 到 nums[end] 的元素和)。
初始狀態下,start 和 end 都指向下標 0,sum 的值為 0。
每一輪迭代,將nums[end] 加到sum,如果sum≥s,則更新子數組的最小長度(此時子數組的長度是end?start+1),然后將nums[start] 從sum 中減去并將start 右移,直到sum<s,在此過程中同樣更新子數組的最小長度。在每一輪迭代的最后,將end 右移。
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:# 雙指針# 如果數組為0,則返回0if not nums:return 0# 初始化參數n = len(nums)ans = n+1start, end = 0, 0total = 0while end < n:total += nums[end]while total >= s:ans = min(ans, end - start + 1)total -= nums[start]start += 1end += 1return 0 if ans == n+1 else ans