209. 长度最小的子数组

1. 题目

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

2. 思路

  • 已知题目中包含的均为正整数，且要求的是满足其和>= target的长度最小的连续子数组，连续意味着不能对数组进行排序操作
  • 本题采用滑动窗口的解法，初始化sum变量用作实时计算窗口范围内的和，初始化l变量作为左指针，初始化r变量作为右指针
  • 初始化result变量为Integer.MAX_VALUE作为结果返回值
  • 初始情况下，左指针l与右指针r均位于0号下标，开启遍历nums数组
  • 在窗口范围内的和sum未满足>= target时，右指针r不断向右移动
  • 当窗口范围内的和sum满足>= target时，记录下标r - l + 1的窗口范围长度，并以此取与现在result两者之间的较小值
  • 当窗口范围内的和sum满足>= target时，左指针l不断向左移动
  • 遍历结束后，当result的值仍然是Integer.MAX_VALUE时，则意味着当前数组无解，返回0
  • 当result的值不是Integer.MAX_VALIE时，正常返回result数值

209.长度最小的子数组.gif

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        var sum = 0;
        var l = 0;
        var r = 0;
        var result = Integer.MAX_VALUE;

        while (r < nums.length) {
            sum += nums[r];
            while (l < nums.length && sum >= target) {
                result = Math.min(r - l + 1, result);
                sum -= nums[l];
                l++;
            }
            r++;
        }

        return Integer.MAX_VALUE == result ? 0 : result;
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

image-20230815183358434