Leetcode209长度最小的子数组

Leetcode 209: 长度最小的子数组 是一道经典的滑动窗口问题，考察多种算法思想，包括双指针、前缀和、二分查找等解法。本题要求找到数组中和大于等于 target 的最短连续子数组长度。

---

题目描述

输入：一个正整数数组 nums 和一个正整数 target。

输出：返回其长度最小的子数组，即和大于等于 target 且长度最短的连续子数组的长度。如果不存在这样的子数组，返回 0。

---

示例输入输出 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是满足和 ≥ 7 的最短子数组。 输入：target = 4, nums = [1,4,4] 输出：1 解释：子数组 [4] 是满足和 ≥ 4 的最短子数组。 输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0 解释：不存在满足情况的子数组。

---

解法 1：滑动窗口（双指针） 思路 滑动窗口是解决数组或字符串中连续子区间问题的经典方法。通过维护一个动态窗口 [start, end] 来实现。具体步骤： 窗口的右边界 end 向右滑动，并逐步累加当前的窗口和。当窗口和 ≥ target 时，尝试移动左边界 start，缩小窗口的大小，并更新满足条件的最小窗口长度。持续调整窗口的范围，直到完全遍历数组。

---

代码模板 class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int left = 0; // 滑动窗口的左边界 int sum = 0; // 当前窗口的总和 int minLength = Integer.MAX_VALUE; for (int right = 0; right < n; right++) { sum += nums[right]; // 移动右边界，累加窗口和 while (sum >= target) { // 当窗口和满足条件时，移动左边界缩小窗口 minLength = Math.min(minLength, right - left + 1); sum -= nums[left]; left++; } } return minLength == Integer.MAX_VALUE ? 0 : minLength; } }

---

复杂度分析 时间复杂度：O(n) 每个元素最多被访问两次：一次是右边界扩展时访问，一次是左边界收缩时访问。 空间复杂度：O(1) 只使用了固定大小的变量，没有额外的数据结构。

---

解法特性 优点：效率高，是解决本题的最佳解法之一，代码精简易理解。适用场景：数组中存在大量连续子数组满足条件的情况。限制：数组元素必须为正数，因滑动窗口无法处理负数。

---

解法 2：前缀和 + 二分查找 思路 前缀和： 构造一个前缀和数组 prefixSum，其中 prefixSum[i] 表示数组前 i 个元素的和。这样，任何子数组 nums[i:j] 的和都可以通过 prefixSum[j] - prefixSum[i] 快速计算得到。 二分查找： 遍历每个前缀和 prefixSum[i]，通过二分查找目标和 prefixSum[i] + target 在前缀和数组中的最早出现位置 j。如果找到有效位置 j，则子数组长度为 j - i，更新最小长度。

---

代码模板 class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int[] prefixSum = new int[n + 1]; // 构造前缀和数组 for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; } int minLength = Integer.MAX_VALUE; // 遍历前缀和数组，使用二分查找目标值 for (int i = 0; i < n; i++) { int requiredSum = prefixSum[i] + target; int boundIndex = binarySearch(prefixSum, requiredSum); // 查找最早满足条件的位置 if (boundIndex != -1) { // 找到有效位置 minLength = Math.min(minLength, boundIndex - i); } } return minLength == Integer.MAX_VALUE ? 0 : minLength; } // 在前缀和中进行二分查找 private int binarySearch(int[] prefixSum, int target) { int low = 0, high = prefixSum.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (prefixSum[mid] >= target) { high = mid - 1; } else { low = mid + 1; } } return low < prefixSum.length ? low : -1; } }

---

复杂度分析 时间复杂度：O(n log n) 构建前缀和数组耗时 O(n)，每次二分查找耗时 O(log n)，遍历数组 O(n)，总复杂度为 O(n log n)。 空间复杂度：O(n) 使用了长度为 n+1 的前缀和数组。

---

解法特性 优点：扩展性强，若 nums 包含负数，不影响正确性。缺点：相较滑动窗口，复杂度偏高，代码较复杂。

---

解法 3：暴力枚举 思路 遍历数组的所有起点 i，计算从 i 开始的每个连续子数组的和。若某个子数组和大于等于 target，更新最小长度。逐一遍历所有可能的子数组，寻找最优解。

---

代码模板 class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int minLength = Integer.MAX_VALUE; // 枚举起点 i for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += nums[j]; if (sum >= target) { minLength = Math.min(minLength, j - i + 1); break; // 提前退出，因为 j 越往后长度越大 } } } return minLength == Integer.MAX_VALUE ? 0 : minLength; } }

---

复杂度分析 时间复杂度：O(n²) 两层嵌套循环，计算所有可能的子数组和。 空间复杂度：O(1) 没有使用额外数据结构。

---

解法特性 优点：实现起来直观简单，易于理解和验证。缺点：性能较低，适用于数组长度较小的情况下。

---

快速 AC 策略 如果需要高效解法，首选 滑动窗口法 (解法 1)： 时间复杂度 O(n)，空间复杂度 O(1)。适用于绝大部分场景。 如果题目数据允许多种解法： 使用 前缀和 + 二分查找法 (解法 2)，适用于需要扩展到含有负数或其他变种的情况。 对于非常小规模的输入或竞赛中快速验证答案： 使用 暴力解法 (解法 3)，易于实现，但效率较低。

无论是面试还是竞赛，熟练掌握滑动窗口模板，就可以快速 AC 本题！