网站导航
> 技术文档 > LeetCode第209题_长度最小的子数组

LeetCode第209题_长度最小的子数组

网友: 技术文档 2025-07-30 13:52:46

LeetCode 第209题：长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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^5

解题思路

方法一：暴力法

最直接的方法是遍历所有可能的子数组，计算每个子数组的和，找出满足条件的最短子数组。

关键点：

  1. 使用两重循环，外循环枚举子数组的起始位置，内循环枚举子数组的结束位置
  2. 计算子数组和，如果大于等于目标值，则更新最短长度

时间复杂度：O(n²)，其中n是数组长度
空间复杂度：O(1)

这种方法可能会在数组较大时超时。

方法二：滑动窗口

滑动窗口是一种更高效的方法。我们可以使用两个指针left和right维护一个窗口，使窗口内的元素和大于等于target，然后尝试缩小窗口。

关键点：

  1. 初始化left和right指针为0，sum为0，minLength为无穷大
  2. 向右移动right指针，累加sum，直到sum大于等于target
  3. 一旦sum大于等于target，尝试移动left指针，减小窗口大小
  4. 更新minLength为当前窗口大小和已知minLength的较小值
  5. 重复2-4，直到right指针到达数组末尾

时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)

方法三：前缀和 + 二分查找

我们也可以使用前缀和加二分查找的方法。

关键点：

  1. 计算前缀和数组sums，其中sums[i]表示nums[0]到nums[i-1]的和
  2. 对于每个前缀和sums[i]，二分查找满足sums[j]-sums[i]>=target的最小j
  3. 更新minLength为min(minLength, j-i)

时间复杂度：O(n log n)
空间复杂度：O(n)，用于存储前缀和数组

代码实现

C# 实现

方法一：暴力法（可能超时）
public class Solution { public int MinSubArrayLen(int target, int[] nums) { int n = nums.Length; int minLength = int.MaxValue; 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; // 找到满足条件的子数组后，不需要继续增加结束位置 } } } return minLength == int.MaxValue ? 0 : minLength; }}
方法二：滑动窗口
public class Solution { public int MinSubArrayLen(int target, int[] nums) { int n = nums.Length; int left = 0; int sum = 0; int minLength = int.MaxValue; for (int right = 0; right < n; right++) { sum += nums[right]; // 当前窗口和大于等于target时，尝试缩小窗口 while (sum >= target) { minLength = Math.Min(minLength, right - left + 1); sum -= nums[left]; left++; } } return minLength == int.MaxValue ? 0 : minLength; }}
方法三：前缀和 + 二分查找
public class Solution { public int MinSubArrayLen(int target, int[] nums) { int n = nums.Length; int minLength = int.MaxValue; // 计算前缀和 int[] sums = new int[n + 1]; for (int i = 1; i <= n; i++) { sums[i] = sums[i - 1] + nums[i - 1]; } // 对于每个前缀和，二分查找 for (int i = 0; i <= n; i++) { int toFind = target + sums[i]; int index = Array.BinarySearch(sums, toFind); // 如果没有找到精确的值，BinarySearch返回一个负数，表示应该插入的位置 if (index < 0) { index = ~index; // 将负数转换为应该插入的位置 } if (index <= n) { minLength = Math.Min(minLength, index - i); } } return minLength == int.MaxValue ? 0 : minLength; }}

Python 实现

方法一：暴力法（可能超时）
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) min_length = float(\'inf\') for i in range(n): sum_val = 0 for j in range(i, n): sum_val += nums[j] if sum_val >= target:  min_length = min(min_length, j - i + 1)  break return min_length if min_length != float(\'inf\') else 0
方法二：滑动窗口
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) left = 0 sum_val = 0 min_length = float(\'inf\') for right in range(n): sum_val += nums[right] # 当前窗口和大于等于target时，尝试缩小窗口 while sum_val >= target: min_length = min(min_length, right - left + 1) sum_val -= nums[left] left += 1 return min_length if min_length != float(\'inf\') else 0
方法三：前缀和 + 二分查找
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) min_length = float(\'inf\') # 计算前缀和 sums = [0] * (n + 1) for i in range(1, n + 1): sums[i] = sums[i - 1] + nums[i - 1] # 对于每个前缀和，二分查找 for i in range(n + 1): to_find = target + sums[i] index = self.binary_search(sums, to_find) if index <= n: min_length = min(min_length, index - i) return min_length if min_length != float(\'inf\') else 0 def binary_search(self, arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] >= target: right = mid - 1 else: left = mid + 1 return left

C++ 实现

方法一：暴力法（可能超时）
class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int minLength = INT_MAX; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += nums[j]; if (sum >= target) {  minLength = min(minLength, j - i + 1);  break; } } } return minLength == INT_MAX ? 0 : minLength; }};
方法二：滑动窗口
class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int left = 0; int sum = 0; int minLength = INT_MAX; for (int right = 0; right < n; right++) { sum += nums[right]; // 当前窗口和大于等于target时，尝试缩小窗口 while (sum >= target) { minLength = min(minLength, right - left + 1); sum -= nums[left]; left++; } } return minLength == INT_MAX ? 0 : minLength; }};
方法三：前缀和 + 二分查找
class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int minLength = INT_MAX; // 计算前缀和 vector<int> sums(n + 1, 0); for (int i = 1; i <= n; i++) { sums[i] = sums[i - 1] + nums[i - 1]; } // 对于每个前缀和，二分查找 for (int i = 0; i <= n; i++) { int toFind = target + sums[i]; auto index = lower_bound(sums.begin(), sums.end(), toFind) - sums.begin(); if (index <= n) { minLength = min(minLength, static_cast<int>(index - i)); } } return minLength == INT_MAX ? 0 : minLength; }};

性能分析

各语言实现的性能对比：

实现语言 方法 执行用时 内存消耗 特点 C# 暴力法 超时 - 简单易懂，但效率低 C# 滑动窗口 92 ms 41.1 MB 最优性能，常数空间 C# 前缀和+二分查找 128 ms 41.4 MB 需要额外空间，但有较好性能 Python 暴力法 超时 - 简单易懂，但效率低 Python 滑动窗口 36 ms 17.3 MB 最优性能，常数空间 Python 前缀和+二分查找 48 ms 17.9 MB 需要额外空间，但有较好性能 C++ 暴力法 超时 - 简单易懂，但效率低 C++ 滑动窗口 4 ms 10.5 MB 最优性能，常数空间 C++ 前缀和+二分查找 8 ms 10.9 MB 需要额外空间，但有较好性能

补充说明

代码亮点

  1. 滑动窗口方法使用两个指针灵活调整窗口大小，避免不必要的计算
  2. 前缀和+二分查找使用了已有的数据结构和算法，提供了另一种时间复杂度为O(n log n)的解法
  3. 所有方法都注意了边界情况的处理，特别是不存在满足条件的子数组时返回0

滑动窗口技巧详解

滑动窗口是一种常用的双指针技巧，特别适用于需要寻找数组（字符串）中的连续子序列的问题。其核心思想是：

  1. 使用两个指针表示窗口的左右边界
  2. 右指针不断向右移动扩大窗口，直到窗口满足特定条件
  3. 一旦条件满足，左指针向右移动缩小窗口，直到条件不再满足
  4. 在这个过程中记录满足条件的最优结果

这种技巧将时间复杂度从O(n²)降低到O(n)，因为每个元素最多被访问两次（一次被right访问，一次被left访问）。

常见错误

  1. 忘记判断不存在满足条件的子数组的情况
  2. 在更新minLength时使用了错误的窗口大小计算
  3. 没有正确处理滑动窗口收缩条件，导致错过最优解
  4. 二分查找实现错误，没有处理找不到精确值的情况

相关题目

  • 3. 无重复字符的最长子串
  • 76. 最小覆盖子串
  • 713. 乘积小于K的子数组
  • 1004. 最大连续1的个数 III
网络标签：

相关问题