文章目錄
- @[toc]
- 題目描述
- 樣例輸入輸出與解釋
- 樣例1
- 樣例2
- 樣例3
- 提示
- 進階
- Python實現
- 前綴和+二分查找
- 滑動窗口
文章目錄
- @[toc]
- 題目描述
- 樣例輸入輸出與解釋
- 樣例1
- 樣例2
- 樣例3
- 提示
- 進階
- Python實現
- 前綴和+二分查找
- 滑動窗口
個人主頁：丷從心·
系列專欄：LeetCode
刷題指南：LeetCode刷題指南
題目描述
- 給定一個含有
n個正整數的數組和一個正整數target - 找出該數組中滿足其總和大于等于
target的長度最小的連續子數組[numsl, numsl+1, ..., numsr-1, numsr]，并返回其長度 - 如果不存在符合條件的子數組，返回
0
樣例輸入輸出與解釋
樣例1
- 輸入：
target = 7，nums = [2,3,1,2,4,3] - 輸出：
2 - 解釋：子數組
[4,3]是該條件下的長度最小的子數組
樣例2
- 輸入：
target = 4，nums = [1,4,4] - 輸出：
1
樣例3
- 輸入：
target = 11，nums = [1,1,1,1,1,1,1,1] - 輸出：
0
提示
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5
進階
- 如果已經實現
O(n)時間復雜度的解法，嘗試設計一個O(nlog(n))時間復雜度的解法
Python實現
前綴和+二分查找
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) -> int:n = len(nums)res = n + 1sums = [0]for i in range(n):sums.append(sums[-1] + nums[i])for i in range(1, n + 1):target = sums[i - 1] + sbound = bisect.bisect_left(sums, target)if bound != len(sums):res = min(res, bound - (i - 1))return res if res != n + 1 else 0
滑動窗口
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)res, sum = n + 1, 0start, end = 0, 0while end < n:sum += nums[end]while sum >= target:res = min(res, end - start + 1)sum -= nums[start]start += 1end += 1return res if res != n + 1 else 0
)
)
