题目:
给定一个含有 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 <= 109
-
1 <= nums.length <= 105
-
1 <= nums[i] <= 104
思路如下:
解法一:滑动窗口
-
以右指针为准遍历,倘若区间内[left, right] (左闭右闭)的和未达到target,直接向右。
-
如果区间内的数大于等于target,则一步步缩小左边起始位置,即缩小窗口。直至区间内的数严格小于target
| 很重要,是 >=。因为我们会记录下等于时刻的长度。如果漏了可能会发现结果始终比答案多1,甚至错解
-
直至结束。
时间复杂度:O(n)
解法二:前缀和 + 二分搜索
时间复杂度:O(nlogn)
题解如下:
#解法一:滑动窗口
class Solution:def minSubArrayLen(self, target, nums):""":type: target: int, nums: List[int]:rtype: int"""left = 0ans = inf # 初始化为无穷大,便于后续取最小值s = 0 # 统计窗口内的和for right, x in enumerate(nums):s += x # 扩展右边界,累加元素值while s >= target: # 当窗口和满足条件时,尝试收缩左边界ans = min(ans,right-left+1)# 更新最小长度s -= nums[left] # 收缩左边界,减去左指针元素left += 1 # 左指针右移return ans if ans < inf else 0 # 处理不存在有效子数组的情况
#解法二:前缀和 + 二分搜索
class Solution:def minSubArrayLen(self, s, nums):""":type: target: int, nums: List[int]:rtype: int因为题目给出 1 <= nums[i] <= 105, 那么可以使用前缀和 加二分查找做1. 因为元素都大于0,所以前缀和肯定是递增的2. 我们以每一个元素为起始位置,二分找第一个大于 target的重点位置, 比较那个最小二分查找一次是 logn, 一共查找n次那么时间复杂度为 O(nlogn)"""n = len(nums)# 1. 计算前缀和, 初始长度为 n + 1, 方便计算. 任意 长度的和,均等于 prefix[i] - prefix[i - 1]prefix = [0] * (n + 1)for i in range(0, n):prefix[i + 1] = prefix[i] + nums[i]# 2. 定义二分查找方法def binarySreach(nums, start, target):"""1. 这里要理清楚, 假如 nums = 1 2 3 4, prefix是 0 1 3 6 10 长度是 n + 1.2. 依次遍历 nums, start 假如为1, 对应 nums的元素2, 前缀和prefix里对应的是 3, 下标为 2! 计算nums里 2 + 3 + 4 的和, 对应到 prefix里是 prefix[n] - prefix[1], 所以搜索起来是从 start + 1开始到最后3. start对应 nums元素下标, start + 1 对应的是 prefix中, 此元素的前缀和。"""left = start + 1# 这里的nums 是 prefixright = len(nums) - 1while left < right:middle = (left + right) // 2 if nums[middle] - nums[start] >= target:right = middleelse:left = middle + 1# 看最后一个位置 是否符合,有可能小于return left - start if nums[left] - nums[start] >= target else n + 1# 3. 寻找满足条件长度最小子数组minLength = n + 1# 使 nums 前n个元素都作为开始元素, 计算第一个 大于 target的子数组长for i in range(n):length = binarySreach(prefix, i, s)minLength = min(minLength, length)return minLength if minLength != n + 1 else 0
#使用python的标准库
class Solution:def minSubArrayLen(self, target, nums):""":type: target: int, nums: List[int]:rtype: int"""n = len(nums)prefix = [0] * (n + 1)for i in range(n):prefix[i + 1] = prefix[i] + nums[i]min_length = n + 1for i in range(n):# 在 prefix[i+1..n] 中查找第一个 >= prefix[i] + target 的位置j = bisect_left(prefix, prefix[i] + target, i + 1, n + 1)if j <= n:min_length = min(min_length, j - i)return min_length if min_length <= n else 0
bisect_left(prefix, prefix[i] + target, i+1, n+1):
在 prefix 中从位置 i+1 到 n+1 查找第一个 >= prefix[i] + target 的位置。