考察点:滑动窗口在「子数组求和」场景的应用;窗口何时扩张、何时收缩;与前缀和+二分两种解法的对比。属编程题。
要点:
win;当 win >= s 时记录长度并尝试收缩左指针(减掉 nums[left] 后若仍 >= s 继续缩),直到不满足。每次收缩都更新最小长度。 def minSubArrayLen(s, nums):
left = 0
win = 0
best = float('inf')
for right, x in enumerate(nums):
win += x
while win >= s:
best = min(best, right - left + 1)
win -= nums[left]
left += 1
return best if best != float('inf') else 0
pre,对每个 i 二分找最小的 j 使 pre[j]-pre[i] >= s,时间 O(n log n);当数组含负数或要查「恰好等于」时二分更通用,但本题全正数下滑动窗口更优。题目与答案就在本页;收藏、批注和错题重练在应用内