LeetCode 209. 长度最小的子数组

约 4 分钟
文章信息 17 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 50-100 字节跳动 微软 美团 快手 腾讯 百度 滴滴 华为 哔哩哔哩 小红书 面试经典 150 题
标签
数组 二分查找 滑动窗口 前缀和 滑动窗口经典题 子数组问题
目录

题目描述

✅ 209. 长度最小的子数组

image-20250418160436467

题意分析

给定一个正整数数组和目标值 target，找出和大于等于 target 的最短连续子数组，返回其长度；不存在则返回 0。

三个信号值得抓住。第一，要的是连续子数组，不是任选子集，候选区间由左右两个端点完全确定。第二，求的是最短而不是最长：一段区间一旦达标，把它继续往右扩只会更长，不可能贡献更优答案，反而应该问「左端还能不能砍掉一点」。第三，元素全为正数，这意味着区间和随右端扩张严格变大、随左端收缩严格变小——这条单调性是后面所有做法的前提，题目特意把它写进约束不是巧合。

边界上注意条件是「大于等于」而非「等于」；若全数组的和都够不到 target，返回 0。

解法：滑动窗口收缩满足条件的区间

核心思路

问题关键：数组元素全为正数。右端加入元素只会让窗口和变大，左端移出元素只会让窗口和变小，因此两个边界都可以单向右移，不必重新枚举区间。

为什么选滑动窗口：暴力枚举左右端点需要 $O(n^2)$；利用正数带来的单调性，右端负责让窗口达标，达标后左端尽量收缩，就能在线性时间内找到每个右端点对应的最短可行窗口。

窗口不变量：sum 始终等于 [left, right] 的元素和。每次右扩后，用 while (sum >= target) 依次记录并收缩所有达标窗口；循环退出时窗口不达标，而且所有以当前 right 结尾的可行窗口都已被检查。

解题步骤

  1. 初始化 left = 0、sum = 0，并用 n + 1 表示“尚未找到答案”。
  2. 右指针逐个加入元素，扩大窗口直到 sum >= target。
  3. 窗口达标时，先更新长度，再移出 nums[left] 并右移 left；持续收缩直到不达标。
  4. 扫描结束后，若答案仍为哨兵则返回 0，否则返回最短长度。

例如 target=7, nums=[2,3,1,2,4,3]，窗口依次找到长度 4、3、2，最终最短窗口为 [4,3]。

代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int ans = nums.length + 1;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }
        return ans == nums.length + 1 ? 0 : ans;
    }
}

func minSubArrayLen(target int, nums []int) int {
    left := 0
    sum := 0
    ans := len(nums) + 1

    for right := 0; right < len(nums); right++ {
        sum += nums[right]
        for sum >= target {
            if right-left+1 < ans {
                ans = right - left + 1
            }
            sum -= nums[left]
            left++
        }
    }

    if ans == len(nums)+1 {
        return 0
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。虽然有嵌套循环，但每个元素最多进入、离开窗口各一次。
  • 空间复杂度：$O(1)$。

关键点总结

  • 使用滑动窗口的前提是正数带来的单调性；若允许负数，本解法不成立。
  • 求最短长度时采用“达标就收缩”，并且必须先记录当前合法窗口。
  • while 会检查同一个右端点下的所有可行左端点，if 只能收缩一次。
  • 若数组含负数，需要改用前缀和与单调队列，而不是强行套窗口。

易错点总结

  • 用 if 代替 while：target=7, [1,1,1,7] 只能收缩一次，会错过长度为 1 的 [7]。
  • 收缩后才更新答案：窗口可能已经不合法，却被错误记录；应先记 right-left+1。
  • 条件写成 sum > target：会漏掉和恰好等于 target 的窗口。
  • 忘记无解转换：target=100, nums=[1,2,3] 应返回 0，而不是哨兵 n+1。

相似题目

题目 难度 考察点
713. 乘积小于 K 的子数组 中等 条件反向：违规才收缩，按右端点统计合法子数组个数
1658. 将 x 减到 0 的最小操作数 中等 问题取反：两端删最少等价于中间留最长的和为 sum - x 窗口
862. 和至少为 K 的最短子数组 困难 允许负数：窗口失效，改用前缀和加单调双端队列
560. 和为 K 的子数组 中等 求恰好等于且含负数：前缀和加哈希计数而非双指针
LCR 008. 长度最小的子数组 中等 与 209 同题，练习「达标即收缩」的标准骨架
LCR 009. 乘积小于 K 的子数组 中等 与 713 同题，巩固另一方向的收缩条件