跳至主要內容

长度最小的子数组：滑动窗口最小长度模板详解

老张2026/4/30大约 6 分钟

长度最小的子数组：滑动窗口最小长度模板详解

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 17 分钟 | 难度：⭐⭐⭐

开篇故事

滑动窗口是处理子数组/子字符串问题的利器。在我做过的 100 多道算法题里，大概有 20 道可以用滑动窗口解决。但很多人搞不清楚滑动窗口模板——到底是先移动右端，还是先移动左端？条件满足时收缩，还是条件不满足时收缩？

其实滑动窗口有两种经典形态：

  1. 最小窗口：不断扩大窗口直到满足条件，然后尽量收缩窗口取最小长度。（本题）
  2. 最大窗口：不断扩大窗口，一旦违反条件就收缩，记录过程中的最大长度。（424、567 等）

LeetCode 209 是"最小窗口"的最简单版本，用它来建立滑动窗口的直觉，是最好的起点。

一、题目解析

题目（LeetCode 209）： 给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 >= target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • target = 7，nums = [2,3,1,2,4,3]，输出：2（[4,3] 和为 7）
  • target = 4，nums = [1,4,4]，输出：1
  • target = 11，nums = [1,1,1,1,1,1,1,1]，输出：0

二、解法一：暴力枚举 O(n²)

public class Solution1 {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, minLen = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;  // 已经找到以 i 为起点的最短子数组
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

复杂度分析

  • 时间复杂度：O(n²)。
  • 空间复杂度：O(1)。

三、解法二：前缀和 + 二分查找 O(n log n)

public class Solution2 {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, minLen = Integer.MAX_VALUE;
        int[] prefix = new int[n + 1];  // prefix[i] = sum(nums[0..i-1])
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }

        for (int i = 1; i <= n; i++) {
            int need = target + prefix[i - 1];  // 找 prefix[j] >= need 的最小 j
            // 在 prefix 上二分找第一个 >= need 的位置
            int lo = i, hi = n;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (prefix[mid] >= need) hi = mid;
                else lo = mid + 1;
            }
            if (lo <= n && prefix[lo] >= need) {
                minLen = Math.min(minLen, lo - i + 1);
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

复杂度分析

  • 时间复杂度：O(n log n)。
  • 空间复杂度：O(n)。前缀和数组。

四、解法三最优：滑动窗口 O(n)

滑动窗口核心思路

对于"最小子数组长度"问题，使用"先扩张，满足后收缩"的窗口：

  1. right 不断右移，把 nums[right] 加入窗口。
  2. 一旦窗口内的和 >= target（满足条件），记录当前窗口长度，然后 left 右移收缩窗口（看能不能更短），继续检查是否还满足条件。
  3. 直到 right 到达末尾。

为什么这是 O(n)？ left 和 right 各自只向右移动，总移动次数 <= 2n。

滑动窗口模板（最小长度版）

int left = 0, windowSum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < n; right++) {
    // 1. 扩大窗口：将 right 处元素加入
    windowSum += nums[right];
    // 2. 收缩窗口：当满足条件时，尝试缩小
    while (windowSum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        windowSum -= nums[left];
        left++;
    }
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;

Mermaid 图

完整代码

public class Solution3 {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int windowSum = 0;
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            // 扩大窗口：纳入 right 处元素
            windowSum += nums[right];

            // 收缩窗口：只要满足条件，就尝试缩小（更新答案 + 收缩左端）
            while (windowSum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                windowSum -= nums[left];
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(sol.minSubArrayLen(7, new int[]{2,3,1,2,4,3})); // 2
        System.out.println(sol.minSubArrayLen(4, new int[]{1,4,4}));       // 1
        System.out.println(sol.minSubArrayLen(11, new int[]{1,1,1,1,1,1,1,1})); // 0
        System.out.println(sol.minSubArrayLen(15, new int[]{1,2,3,4,5})); // 5
    }
}

复杂度分析

  • 时间复杂度：O(n)。right 移动 n 次，left 移动最多 n 次，总计 O(2n)。
  • 空间复杂度：O(1)。

五、举一反三：滑动窗口最小长度类题目

题号题目窗口条件
76最小覆盖子串窗口内包含所有目标字符
904水果成篮窗口内最多 2 种不同水果
862和至少为 K 的最短子数组含负数，需要单调队列辅助

最小窗口通用模板：

int left = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < n; right++) {
    // 扩大窗口
    add(nums[right]);
    // 收缩窗口（当满足条件时）
    while (condition()) {
        minLen = Math.min(minLen, right - left + 1);
        remove(nums[left]);
        left++;
    }
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;

最大窗口通用模板（另一类）：

int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    // 扩大窗口
    add(nums[right]);
    // 收缩窗口（当违反条件时）
    while (!condition()) {
        remove(nums[left]);
        left++;
    }
    // 此时窗口合法，记录最大长度
    maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;

六、踩坑实录

坑一：收缩窗口时忘记更新答案

一些人把更新 minLen 放在了 right 循环的末尾，而不是在 while 收缩循环内。这会导致只在每次扩大时检查，而错过了收缩过程中可能出现的更小长度。正确位置是：在 while 循环内，每次收缩前先更新 minLen，然后再执行收缩。

坑二：用 if 而不是 while 收缩

用 if (condition) { ... left++; } 而不是 while (condition) { ... left++; }，导致每次最多收缩一步。对于"最小长度"问题，一旦满足条件，应该尽量收缩，而不是只收缩一次。while 确保了尽量收缩到不满足条件为止。

坑三：nums 包含 0 时的特殊情况

如果 nums 包含 0，窗口和不变，while 循环可能多次执行而 sum 不减小，导致左指针越过右指针。但题目说"正整数"，所以不会有 0。如果遇到含 0 的变种题目，需要额外处理。

坑四：target == 0 时的逻辑

如果 target == 0（题目不会出现，但扩展题目可能有），所有子数组都满足条件，最小长度是 1（单个元素）。通用模板在这种情况下需要额外判断，因为 while (windowSum >= 0) 会无限循环。

坑五：没有元素满足条件时返回 0

minLen 初始化为 Integer.MAX_VALUE，最终没有更新过则返回 0，这是题目要求的。忘记这个检查直接返回 minLen 会导致在无解情况下返回 2147483647。

七、总结

滑动窗口"最小长度"模板的框架：right 不断右移扩大窗口；一旦满足条件，记录长度并 left++ 收缩，直到不再满足条件；right 继续前进。

关键理解：

  • 扩大窗口：纳入 right（在外层 for 循环）
  • 收缩窗口：用 while 循环（不是 if）
  • 更新答案：在 while 内部，每次收缩前

这个模板和"最大长度"模板的区别在于更新答案的时机：最小长度在收缩时更新，最大长度在收缩后（窗口合法时）更新。搞清楚这个区别，大部分滑动窗口题目就迎刃而解了。

编辑此页
最近更新:
贡献者: xiaozhangge