文章目錄

• • @[toc]
  • • 題目描述
    • 樣例輸入輸出與解釋
    • • 樣例1
      • 樣例2
      • 樣例3
    • 提示
    • 進(jìn)階
    • Python實(shí)現(xiàn)
    • • 前綴和+二分查找
      • 滑動(dòng)窗口

個(gè)人主頁：丷從心·

系列專欄：LeetCode

刷題指南：LeetCode刷題指南

---

題目描述

• 給定一個(gè)含有n個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù)target
• 找出該數(shù)組中滿足其總和大于等于target的長度最小的連續(xù)子數(shù)組[numsl, numsl+1, ..., numsr-1, numsr]，并返回其長度
• 如果不存在符合條件的子數(shù)組，返回0

---

樣例輸入輸出與解釋

樣例1

• 輸入：target = 7，nums = [2,3,1,2,4,3]
• 輸出：2
• 解釋：子數(shù)組[4,3]是該條件下的長度最小的子數(shù)組

樣例2

• 輸入：target = 4，nums = [1,4,4]
• 輸出：1

樣例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ìn)階

• 如果已經(jīng)實(shí)現(xiàn)O(n)時(shí)間復(fù)雜度的解法，嘗試設(shè)計(jì)一個(gè)O(nlog(n))時(shí)間復(fù)雜度的解法

---

Python實(shí)現(xiàn)

前綴和+二分查找

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

滑動(dòng)窗口

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

---