LeetCode209:MinSubArrayLen


LeetCode地址

滑动窗口解题思路

初始化变量和窗口

  • 定义两个指针 left 和 right，分别表示窗口的左右边界，初始化为0。
  • 定义一个变量 sum 用于存储窗口内元素的和，初始值为0。
  • 定义一个变量 minlength 用于记录符合条件的最短子数组的长度，初始值为0。

移动右边界，扩大窗口

  • 在一个 while 循环中，不断将 nums[right] 加到 sum 中，然后将右指针 right 向右移动，扩大窗口。

    移动左边界，缩小窗口

  • 如果当前窗口的和大于等于目标值 target，则在另一个内部的 while 循环中，不断将 nums[left] 从 sum 中减去，并将左指针 left 向右移动，缩小窗口，直到窗口内的和小于目标值。
  • 在这个过程中，不断更新 minlength，保持其为符合条件的最短子数组的长度。

    循环直到右指针到达数组末尾

  • 不断执行步骤2和步骤3，直到右指针 right 到达数组的末尾。

    返回结果

  • 返回 minlength，即为符合条件的最短子数组的长度。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int minSubArrayLen(int target, int[] nums) {
        int left = 0; // 左指针
        int right = 0; // 右指针
        int sum = 0; // 子数组和
        int minlength = 0; // 最小子数组长度
        while (right < nums.length) {
            sum += nums[right]; // 添加当前元素到和
            while (sum >= target) { // 当和大于等于目标值时
                if (right - left + 1 < minlength || minlength == 0) { // 如果当前子数组长度小于之前的子数组长度
                    minlength = right - left + 1; // 更新最小子数组长度
                }
                sum -= nums[left]; // 从左边移除元素，减小和
                left++; // 左指针向右移动
            }
            right++; // 右指针向右移动
        }
        return minlength; // 返回最小子数组长度
    }

双指针解题思路

初始化变量和窗口

  • size 表示数组的长度，ans 用于记录符合条件的最短子数组的长度，初始化为 size + 1，确保初始值大于任何可能的子数组长度。
  • l 表示窗口的左边界，初始化为0。
  • sum 表示窗口内元素的和，初始化为0。

    移动右边界，扩大窗口

  • 使用一个 for 循环，遍历数组，移动右指针 r，将 nums[r] 加到 sum 中，扩大窗口。

    移动左边界，缩小窗口

  • 在一个内部的 while 循环中，如果当前窗口的和大于等于目标值 target，则计算当前子数组的长度 r - l + 1，并更新 ans 为较小的值，即 Math.min(ans, r - l + 1)。
  • 然后将窗口的左边界向右移动，即 sum -= nums[l++]，缩小窗口。

    循环直到右指针到达数组末尾

  • 不断执行步骤2和步骤3，直到右指针 r 到达数组的末尾。

    返回结果

  • 返回 ans，即为符合条件的最短子数组的长度。如果 ans 的值没有被更新，说明没有符合条件的子数组，返回0。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     // 双指针
    public static int minSubArrayLen03(int target, int[] nums) {
        int left = 0, right = 0, min = Integer.MAX_VALUE, sum = 0;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= target) {
                min = Math.min(min, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        return min <= nums.length ? min : 0;
    }