文章目录
- @[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^9
1 <= nums.length <= 10^5
1 <= 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