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

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

标题描述

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

中等
标题链接

点击在LeetCode中查察标题
示例

示例 1：

1. 输入：target = 7, nums = [2,3,1,2,4,3]
2. 输出：2
3. 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

复制代码

示例 2：

1. 输入：target = 4, nums = [1,4,4]
2. 输出：1

复制代码

示例 3：

1. 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
2. 输出：0

复制代码

提示

• 1 <= target <= 10^9
  
• 1 <= nums.length <= 10^5
  
• 1 <= nums <= 10^5
  

解题思绪

方法一：暴力法

最直接的方法是遍历全部可能的子数组，计算每个子数组的和，找出满足条件的最短子数组。
关键点：

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

时间复杂度：O(n²)，其中n是数组长度
空间复杂度：O(1)
这种方法可能会在数组较大时超时。
方法二：滑动窗口

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

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

时间复杂度：O(n)，每个元素最多被访问两次
空间复杂度：O(1)
方法三：前缀和 + 二分查找

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

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

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

C# 实现

方法一：暴力法（可能超时）

1. public class Solution {
2.     public int MinSubArrayLen(int target, int[] nums) {
3.         int n = nums.Length;
4.         int minLength = int.MaxValue;
5.         
6.         for (int i = 0; i < n; i++) {
7.             int sum = 0;
8.             for (int j = i; j < n; j++) {
9.                 sum += nums[j];
10.                 if (sum >= target) {
11.                     minLength = Math.Min(minLength, j - i + 1);
12.                     break; // 找到满足条件的子数组后，不需要继续增加结束位置
13.                 }
14.             }
15.         }
16.         
17.         return minLength == int.MaxValue ? 0 : minLength;
18.     }
19. }

复制代码

方法二：滑动窗口

1. public class Solution {
2.     public int MinSubArrayLen(int target, int[] nums) {
3.         int n = nums.Length;
4.         int left = 0;
5.         int sum = 0;
6.         int minLength = int.MaxValue;
7.         
8.         for (int right = 0; right < n; right++) {
9.             sum += nums[right];
10.             
11.             // 当前窗口和大于等于target时，尝试缩小窗口
12.             while (sum >= target) {
13.                 minLength = Math.Min(minLength, right - left + 1);
14.                 sum -= nums[left];
15.                 left++;
16.             }
17.         }
18.         
19.         return minLength == int.MaxValue ? 0 : minLength;
20.     }
21. }

复制代码

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

1. public class Solution {
2.     public int MinSubArrayLen(int target, int[] nums) {
3.         int n = nums.Length;
4.         int minLength = int.MaxValue;
5.         
6.         // 计算前缀和
7.         int[] sums = new int[n + 1];
8.         for (int i = 1; i <= n; i++) {
9.             sums[i] = sums[i - 1] + nums[i - 1];
10.         }
11.         
12.         // 对于每个前缀和，二分查找
13.         for (int i = 0; i <= n; i++) {
14.             int toFind = target + sums[i];
15.             int index = Array.BinarySearch(sums, toFind);
16.             
17.             // 如果没有找到精确的值，BinarySearch返回一个负数，表示应该插入的位置
18.             if (index < 0) {
19.                 index = ~index; // 将负数转换为应该插入的位置
20.             }
21.             
22.             if (index <= n) {
23.                 minLength = Math.Min(minLength, index - i);
24.             }
25.         }
26.         
27.         return minLength == int.MaxValue ? 0 : minLength;
28.     }
29. }

复制代码

Python 实现

方法一：暴力法（可能超时）

1. class Solution:
2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3.         n = len(nums)
4.         min_length = float('inf')
5.         
6.         for i in range(n):
7.             sum_val = 0
8.             for j in range(i, n):
9.                 sum_val += nums[j]
10.                 if sum_val >= target:
11.                     min_length = min(min_length, j - i + 1)
12.                     break
13.         
14.         return min_length if min_length != float('inf') else 0

复制代码

方法二：滑动窗口

1. class Solution:
2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3.         n = len(nums)
4.         left = 0
5.         sum_val = 0
6.         min_length = float('inf')
7.         
8.         for right in range(n):
9.             sum_val += nums[right]
10.             
11.             # 当前窗口和大于等于target时，尝试缩小窗口
12.             while sum_val >= target:
13.                 min_length = min(min_length, right - left + 1)
14.                 sum_val -= nums[left]
15.                 left += 1
16.         
17.         return min_length if min_length != float('inf') else 0

复制代码

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

1. class Solution:
2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3.         n = len(nums)
4.         min_length = float('inf')
5.         
6.         # 计算前缀和
7.         sums = [0] * (n + 1)
8.         for i in range(1, n + 1):
9.             sums[i] = sums[i - 1] + nums[i - 1]
10.         
11.         # 对于每个前缀和，二分查找
12.         for i in range(n + 1):
13.             to_find = target + sums[i]
14.             index = self.binary_search(sums, to_find)
15.             
16.             if index <= n:
17.                 min_length = min(min_length, index - i)
18.         
19.         return min_length if min_length != float('inf') else 0
20.    
21.     def binary_search(self, arr, target):
22.         left, right = 0, len(arr) - 1
23.         
24.         while left <= right:
25.             mid = (left + right) // 2
26.             if arr[mid] >= target:
27.                 right = mid - 1
28.             else:
29.                 left = mid + 1
30.         
31.         return left

复制代码

C++ 实现

方法一：暴力法（可能超时）

1. class Solution {
2. public:
3.     int minSubArrayLen(int target, vector<int>& nums) {
4.         int n = nums.size();
5.         int minLength = INT_MAX;
6.         
7.         for (int i = 0; i < n; i++) {
8.             int sum = 0;
9.             for (int j = i; j < n; j++) {
10.                 sum += nums[j];
11.                 if (sum >= target) {
12.                     minLength = min(minLength, j - i + 1);
13.                     break;
14.                 }
15.             }
16.         }
17.         
18.         return minLength == INT_MAX ? 0 : minLength;
19.     }
20. };

复制代码

方法二：滑动窗口

1. class Solution {
2. public:
3.     int minSubArrayLen(int target, vector<int>& nums) {
4.         int n = nums.size();
5.         int left = 0;
6.         int sum = 0;
7.         int minLength = INT_MAX;
8.         
9.         for (int right = 0; right < n; right++) {
10.             sum += nums[right];
11.             
12.             // 当前窗口和大于等于target时，尝试缩小窗口
13.             while (sum >= target) {
14.                 minLength = min(minLength, right - left + 1);
15.                 sum -= nums[left];
16.                 left++;
17.             }
18.         }
19.         
20.         return minLength == INT_MAX ? 0 : minLength;
21.     }
22. };

复制代码

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

1. class Solution {
2. public:
3.     int minSubArrayLen(int target, vector<int>& nums) {
4.         int n = nums.size();
5.         int minLength = INT_MAX;
6.         
7.         // 计算前缀和
8.         vector<int> sums(n + 1, 0);
9.         for (int i = 1; i <= n; i++) {
10.             sums[i] = sums[i - 1] + nums[i - 1];
11.         }
12.         
13.         // 对于每个前缀和，二分查找
14.         for (int i = 0; i <= n; i++) {
15.             int toFind = target + sums[i];
16.             auto index = lower_bound(sums.begin(), sums.end(), toFind) - sums.begin();
17.             
18.             if (index <= n) {
19.                 minLength = min(minLength, static_cast<int>(index - i));
20.             }
21.         }
22.         
23.         return minLength == INT_MAX ? 0 : minLength;
24.     }
25. };

复制代码

性能分析

各语言实现的性能对比：
实现语言方法执行用时内存消耗特点C#暴力法超时-简单易懂，但效率低C#滑动窗口92 ms41.1 MB最优性能，常数空间C#前缀和+二分查找128 ms41.4 MB必要额外空间，但有较好性能Python暴力法超时-简单易懂，但效率低Python滑动窗口36 ms17.3 MB最优性能，常数空间Python前缀和+二分查找48 ms17.9 MB必要额外空间，但有较好性能C++暴力法超时-简单易懂，但效率低C++滑动窗口4 ms10.5 MB最优性能，常数空间C++前缀和+二分查找8 ms10.9 MB必要额外空间，但有较好性能增补说明

代码亮点

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

滑动窗口技巧详解

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

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

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

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

相干标题

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