209. 长度最小的子数组
一、题目描述
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
进阶：
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
二、解题思路 & 代码
2.1 方法一：暴力法（Python 超时）
暴力法是最直观的方法。初始化子数组的最小长度为无穷大，枚举数组 nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从nums[i] 到 nums[j] 的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是 j−i+1）。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1
for i in range(n):
total = 0
for j in range(i, n):
total += nums[j]
if total >= s:
ans = min(ans, j - i + 1)
break
return 0 if ans == n + 1 else ans
复杂度分析
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。
- 空间复杂度： O ( 1 ) O(1) O(1)。
2.2 前缀 + 二分
为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 s u m s [ b o u n d ] − s u m s [ i − 1 ] ≥ s sums[bound]−sums[i−1]≥s sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）。
因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。
class Solution:
def binary_search(self, numSum, left, right, target): # 二分查找函数定义
while left <= right:
mid = left + (right - left) // 2
if numSum[mid] >= target:
right = mid-1
elif numSum[mid] < target:
left = mid+1
return left
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if len(nums) == 0:
return 0
n = len(nums)
ans = n+1 # 结果变量
numSum = [0] # 前缀和数组，补一个零是为了防止漏判首个元素
for i in range(n):
numSum.append(numSum[i]+nums[i])
for j in range(1, n+1):
target = numSum[j-1] + s
bound = self.binary_search(numSum, 0, n, target)
if bound != len(numSum):
ans = min(ans, bound-(j-1))
return ans if ans != n+1 else 0
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是O(n)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。
- 空间复杂度：O(n)，其中 n 是数组的长度。额外创建数组 sums 存储前缀和。
2.3 双指针（使用队列相加）
实际上我们也可以把它称作是滑动窗口，这里的队列其实就相当于一个窗口
我们把数组中的元素不停的入队，直到总和大于等于 s 为止，接着记录下队列中元素的个数，然后再不停的出队，直到队列中元素的和小于 s 为止（如果不小于 s，也要记录下队列中元素的个数，这个个数其实就是不小于 s 的连续子数组长度，我们要记录最小的即可）。接着再把数组中的元素添加到队列中……重复上面的操作，直到数组中的元素全部使用完为止。
这里以 [2,3,1,2,4,3] 举例画个图来看下
上面画的是使用队列，但在代码中我们不直接使用队列，我们使用两个指针，一个指向队头一个指向队尾，我们来看下代码
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
n = len(nums)
min_ = float('inf')
start = 0
end = 0
sums = 0
while end < n:
sums += nums[end]
while sums >= s:
min_ = min(min_, end - start + 1)
sums -= nums[start]
start += 1
end += 1
return 0 if min_ == float('inf') else min_
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
- 空间复杂度：O(1)。
参考
==============================================================================================================================
862. 和至少为 K 的最短子数组
一、题目描述
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。
示例 1：
输入：A = [1], K = 1
输出：1
示例 2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3
输出：3
提示：
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
二、解题思路 & 代码
滑动窗口
import collections
class Solution:
def shortestSubarray(self, A: List[int], K: int) -> int:
n=len(A)
dp=[0]*(n+1)
for i in range(n):
dp[i+1]=dp[i]+A[i] #此处dp代表前缀和
ans=n+1
Q=collections.deque() #Q中放起点坐标
for j in range(n+1): #遍历dp
#若栈顶dp[Q[-1]]比dp[j]大，那它一定不如dp[j]优，因为j作为起点比Q[-1]更短，子数组和更有可能>=K.
while Q and dp[Q[-1]] >= dp[j]:
Q.pop()
#此时j作为终点，由Q中dp单调递增，左边的dp更有可能使子数组和>=k，但起点越右子数组越短，所以从左往右找符合条件的最右起点，由于后面符合条件的终点(如y-Q[0])不可能比j-Q[0]更短，所以符合条件的起点用完就pop，不符合条件的起点保留看看后面有没有机会。
while Q and dp[j]-dp[Q[0]] >= K:
ans = min(ans,j-Q.popleft())
Q.append(j)
return ans if ans<=n else -1
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组 A 的长度。
- 空间复杂度：O(N)。
京公网安备 11010502036488号