江川个人博客FIELD NOTES / 个人知识库

Article / 文章

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

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

题目描述

给定一个含有 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. 二分查找实现错误，没有处理找不到精确值的情况

相关题目