力扣数组
209.长度最小的子数组
209.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
题目
给定一个含有 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^4
思路
本题适合用滑动窗口（双指针） 解法，核心是维护一个动态的窗口 [left, right]，通过调整左右指针的位置，找到满足和 ≥ target 的最小窗口长度：
- 初始化左指针 left = 0，当前窗口和 sum = 0，最小长度 result = 无穷大；
- 右指针 right 遍历数组，将 nums[right] 加入 sum；
- 当 sum ≥ target 时，尝试收缩左指针以缩小窗口：
- 计算当前窗口长度（right - left + 1），更新 result 为更小值；
- 从 sum 中减去 nums[left]，并将 left 右移一位；
- 遍历结束后，若 result 仍为无穷大，说明无符合条件的子数组，返回 0；否则返回 result。
该解法时间复杂度为 O(n)（每个元素最多被左右指针各访问一次），空间复杂度为 O(1)，适合处理 10^5 量级的数组。
解法
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = 0
current_sum = 0
min_length = float('inf') # 初始化为无穷大
for right in range(len(nums)):
current_sum += nums[right]
# 当当前和满足条件时，收缩左指针以找最小窗口
while current_sum >= target:
# 更新最小长度
min_length = min(min_length, right - left + 1)
# 收缩左指针
current_sum -= nums[left]
left += 1
# 若未找到符合条件的子数组，返回0，否则返回最小长度
return min_length if min_length != float('inf') else 0解释
| 代码片段 | 作用与原因 |
|---|---|
left = 0 | 初始化滑动窗口左边界，窗口初始为空 |
current_sum = 0 | 记录当前窗口内元素的和，初始为0 |
min_length = float('inf') | 初始化为无穷大，确保任何有效窗口长度都能覆盖它 |
for right in range(len(nums)) | 右指针遍历数组，逐步扩大窗口右边界 |
current_sum += nums[right] | 将当前右指针元素加入窗口和 |
while current_sum >= target | 当窗口和满足条件时，持续收缩左边界（因为要找最小长度） |
min(min_length, right-left+1) | 计算当前窗口长度，更新最小长度 |
current_sum -= nums[left] | 收缩左边界前，先从窗口和中减去左指针元素 |
left += 1 | 左指针右移，缩小窗口 |
min_length != float('inf') | 若仍为无穷大，说明无符合条件的子数组，返回0；否则返回最小长度 |
进阶
1. 二分查找解法
由于数组元素均为正整数，前缀和数组是严格递增的，因此可通过二分查找找每个前缀和对应的最小右边界：
- 计算前缀和数组 pre_sum（pre_sum[0]=0，pre_sum[i] = nums[0]+...+nums[i-1]）；
- 遍历前缀和数组，对每个 pre_sum[i]，找最小的 j 使得 pre_sum[j] - pre_sum[i] ≥ target；
- 通过二分查找在 pre_sum[i+1...] 中找满足条件的最小 j，计算 j-i 作为候选长度；
- 最终返回最小的候选长度（若无则返回0）。
代码实现：
import bisect
def minSubArrayLen(target: int, nums: list[int]) -> int:
pre_sum = [0]
for num in nums:
pre_sum.append(pre_sum[-1] + num)
min_length = float('inf')
for i in range(len(pre_sum)):
# 找最小的j，使得pre_sum[j] >= pre_sum[i] + target
j = bisect.bisect_left(pre_sum, pre_sum[i] + target)
if j < len(pre_sum):
min_length = min(min_length, j - i)
return min_length if min_length != float('inf') else 02. 处理大数据量优化
若 target 极大（如 10^9），滑动窗口解法仍能高效处理，因为一旦 current_sum ≥ target 就会立即收缩窗口，无需遍历全部元素；而二分查找解法的时间复杂度为 O(n log n)，在 n=10^5 时略逊于滑动窗口的 O(n)。
3. 扩展到子数组和等于 target
若要求子数组和等于 target（而非 ≥），滑动窗口仍适用（只需将 while 条件改为 current_sum == target），但需注意：
- 若数组包含负数，滑动窗口不再适用（前缀和非单调），需用哈希表记录前缀和的下标；
- 若数组全为正整数，滑动窗口仍是最优解。