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

特辣的海藻！7

article 2025/3/3 12:15:24

特邀嘉宾：滑动窗口~

题

209. 长度最小的子数组 - 力扣（LeetCode）

做过的题，再一次做，还是有问题。。。。我把它给解决掉！

超时超时超时超时超时超时超时超时超时超时超时超时超时超时超时超时超时

import java.lang.Math;
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, minLen = n+1, sum = 0;
        int[] cnt = new int[n];
        for(int i = 0; i < n; i++) {
            int len = 1;
            sum = nums[i];
            for(int j = i + 1; j < n; j++) {
                
                if(sum >= target){
                    break;
                }
                else{
                    sum += nums[j];
                    len++;
                }
            }
            if(sum >= target)
                minLen = Math.min(len, minLen);
        }
        minLen = minLen == n+1 ? 0 : minLen;
        return minLen;
    }
}

没错但也不推荐没错但也不推荐没错但也不推荐没错但也不推荐没错但也不推荐

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        int len = 0, sum = 0, j = 0, minLen = nums.length+1;
        for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                len++;
                while (sum >= target) {
                    minLen = Math.min(len, minLen);
                    sum -= nums[j];
                    j++;
                    len--;
                }
                
            }
         minLen = minLen == nums.length+1 ? 0 : minLen;
        return minLen;
    }
}

来！看这个！！来！看这个！！来！看这个！！来！看这个！！来！看这个！！

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        int sum = 0, j = 0, minLen = nums.length+1;
        for (int i = 0; i < nums.length; i++) {
                sum += nums[i];;
                while (sum >= target) {
                    minLen = Math.min(i-j+1, minLen);
                    sum -= nums[j];
                    j++;                   
                }
                
            }
         minLen = minLen == nums.length+1 ? 0 : minLen;
        return minLen;
    }
}

这道题用暴力for循环超时，用滑动窗口的思路就是：当满足条件sum大于等于目标值就缩小窗口，寻找下一个可能的答案。

我觉得我当时是没有弄懂滑动窗口的核心要点：

● 在外循环中扩展右边界，内循环中移动左边界

● 逐个扩展右边界，及时收缩左边界（才能覆盖所有子数组）

● 实时记录滑动窗口的长度，用窗口的端点 [j, i]，即 j-i+1，而不是用一个变量

● 先记录长度，再移动指针更改左边界

我就是没有理解领会到到底应该怎样移动这个窗口，是要一个一个移动窗口，逐个元素的扩展有边界，而不是不满足状态时才移动，这样跳跃式移动会错过可能的答案。（比如数组中单个元素就是target值）。还有是用的变量记录数组长度，然后自以为的更新长度时没问题，先缩小窗口，再记录长度就出错。应该要先记录此时窗口的长度，再缩小窗口。