题目信息

题目描述

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

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

初步思路

最容易想到的就是暴力解法，使用两层循环：

  • 第一层循环控制子数组的起始位置 i
  • 第二层循环从 i 开始向后累加，直到总和大于等于 target
  • 每次找到满足条件的长度后，更新最小长度

但是这种方法的时间复杂度是 **O(n²)**，题目中给出 nums.length <= 10^5，显然平方级别的复杂度会超时。

那我们需要寻找更优的解法，这道题适合使用 滑动窗口（Sliding Window） 技巧，本质上就是双指针思想。

算法分析

  • 核心思想：通过左右两个指针维护一个滑动窗口，根据窗口内总和与 target 的关系，动态调整窗口的左右边界
  • 技巧要点：
    1. 右指针 j 不断向右扩展，将元素加入窗口总和
    2. 当窗口总和已经大于等于 target 时，尝试移动左指针 i 缩小窗口，同时更新最小长度，直到窗口总和小于 target
    3. 这样每个元素最多被访问两次（一次被右指针加入，一次被左指针移出），所以时间复杂度可以降到线性
  • 时间复杂度：**O(n)**，每个元素最多进入和离开窗口一次
  • 空间复杂度：**O(1)**，只使用常数额外空间

代码实现（C++）

方法一：暴力解法（会超时）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        for(int i = 0; i < nums.size(); ++i) {
            int sum = 0;
            for(int j = i; j < nums.size(); ++j) {
                sum += nums[j];
                if(sum >= target) {
                    res = min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

方法二：滑动窗口

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0, res = INT_MAX, sum = 0;
        for(int j = 0; j < nums.size(); ++j) {
            sum += nums[j];
            while(sum >= target) {
                res = min(res, j - i + 1);
                sum -= nums[i];
                ++i;
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

测试用例

输入 输出 说明
target = 7, nums = [2,3,1,2,4,3] 2 子数组 [4,3] 是最短的
target = 4, nums = [1,4,4] 1 单个元素 4 就满足条件
target = 11, nums = [1,1,1,1,1,1,1,1] 0 总和都不够，返回 0

总结与反思

滑动窗口是解决连续子数组问题的常用技巧，关键在于：

  1. 确定什么时候移动右指针扩展窗口
  2. 确定什么时候移动左指针收缩窗口
  3. 在收缩窗口的过程中不断更新答案

这道题中因为所有元素都是正整数，所以向右扩展时总和一定增加，向左收缩时总和一定减少，这是滑动窗口能够正确工作的前提。如果数组中有负数，这个方法就不适用了，需要改用前缀树+二分查找的方法。

滑动窗口本质上就是双指针，它能将原本平方复杂度的问题优化到线性复杂度，是非常高效的技巧，需要多多练习掌握。