当前位置：首页 > article >正文

9.《滑动窗口篇》---①长度最小的子数组（中等）

article 2024/11/20 18:56:44

滑动窗口推导过程

我们不能说一上来就知道这个题目用滑动窗口，然后就使用滑动窗口的方法来做这个题目。

首先我们想到的应该是暴力解法。

接着再优化为滑动窗口

由于数字都是 ≥ 0 的数。因此累加的数越多。和越大。

因此right往后遍历的时候。当发现sum > target 就可以不用再往右移动了。

此时left往右移动一位。

按照暴力枚举。right 还需要从新回到left的位置。再次计算累加和是否≥target。

而我们发现 (使用暴力解法的时候两个指针可以不会退。就可以用滑动窗口了)

此时只需要让sum-2 然后再次判断。就可以了。而right不用移动。

这就引入了滑动窗口。

利用单调性，+同向双指针。

滑动窗口的使用：

1. left = 0，right =0；

2.进窗口

3.判断

4.出窗口

方法一：暴力解法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;// 用于存储最短子数组的长度

        for(int i = 0; i < n; i++){
            int sum = 0;// 每次外层循环重新初始化sum
            for(int j =i; j<n; j++){
                sum += nums[j];// 计算子数组的和
                if(sum >= target){// 如果子数组的和大于或等于目标值
                    minLen = Math.min(j-i+1,minLen);// 更新最短长度
                    break;// 提前结束当前内层循环，因为长度已经达到条件
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
        // 如果没有符合条件的子数组，返回0
    }
}

复杂度分析

时间复杂度: O(n2)O(n^2)O(n2)（嵌套双重循环导致的平方复杂度）
空间复杂度: O(1)O(1)O(1)（只使用了常量级别的额外空间）

解法二：滑动窗口（利用单调性+ “同向双指针”）

1.left = 0，right = 0

2.进窗口。我们让right++，并且 sum += nums[right];

3.判断条件。使用while循环判断

4.出窗口：sum -= nums[left++];

注意：

判断条件的时候一定要使用while循环。而不是if。

因为left++一次之后。也可能继续满足条件。

如果使用 if 很可能会漏掉正确答案。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;// 用于存储最短子数组的长度
        int sum = 0;

        for(int left = 0,right =0; right < n; right++){
            sum += nums[right];
            while(sum >= target){
                minLen = Math.min(right-left+1,minLen);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}