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

用户11288958

发布于 2024-11-21 15:17:38

420

文章被收录于专栏：学习

滑动窗口推导过程

我们不能说一上来就知道这个题目用滑动窗口，然后就使用滑动窗口的方法来做这个题目。首先我们想到的应该是暴力解法。接着再优化为滑动窗口由于数字都是 ≥ 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;
    }
}