【LeetCode】【209】长度最小的子数组（1488字）
个人主页：丷从心·
系列专栏：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 + 1
sums = [0]
for i in range(n):
sums.append(sums[-1] + nums[i])
for i in range(1, n + 1):
target = sums[i - 1] + s
bound = 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, 0
start, end = 0, 0
while end < n:
sum += nums[end]
while sum >= target:
res = min(res, end - start + 1)
sum -= nums[start]
start += 1
end += 1
return res if res != n + 1 else 0
原文地址：https://blog.csdn.net/from__2024_04_11/article/details/139067180
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！