• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!

互联网 diligentman 2周前 (10-17) 18次浏览

  嗨,大家好,我是袁厨(因为酷爱做饭,所以自己考取了厨师证)。之前一直看大家写的博客,学到了很多东西。然后最近萌生了自己写的想法,将自己知道的分享给需要的同学。以后每天会为大家分享leetcode精选题目的各种题解,并且每周会整理一下该周刷的所有题目,及解题框架。大家微信搜索【程序员爱做饭】关注我吧!


209,长度最小的子数组

  • 题目描述
  • 暴力解法
    • 做题思路
    • 题目代码
  • 滑动窗口
    • 做题思路
    • 题目代码
  • 总结


题目描述

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!


暴力解法

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!

做题思路

遇到这个题目的第一思路获取就是滑动窗口了,但是我们目前还没有学习滑动窗口,那我们可以先通过暴力解法解决呀,之前一个学长给我说,面试的时候不要管什么方法,你只要把题目做出来,就是好方法,所以我们先想着解决这个问题,然后再进行优化。我的大致思路就是,通过两层循环进行元素累加,第一个循环负责定位起点,然后从起点开始累加之后的元素,直到我们累加和大于等于目标值。然后保留当前子数组的长度,更换下一起点,直到遍历结束。
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
省略了绿指针移动过程
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
最后min的值为2,所以输出2.时间复杂度O(n^2),空间复杂度O(1)

题目代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0;//定义累加的变量
        int childlen = 0;//子数组长度
        int minlen = Integer.MAX_VALUE;//int最大整数,常用
        for(int i = 0 ;i < nums.length ; i++){
            sum = 0;//每次都要归0,因为起点更换
            for(int j = i;j < nums.length ;j++ ){
                sum += nums[j];
                //这里是大于等于,我原来理解错误题目,写的等于,浪费一次提交
                if(sum >= s){
                     //子孩子长度
                    childlen = j-i+1;
                    //最小值
                    minlen = Math.min(minlen,childlen);
                    break;
                }
            }
        }
        //这里不可以直接返回minlen,因为有可能存在不存在子数组的情况。
        return minlen==Integer.MAX_VALUE ? 0: minlen;
    }
}


滑动窗口

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!

做题思路

滑动窗口是数组操作中的一种重要方法,数组中很多题目都可以通过滑动窗口来解决。暴力法中,我们的红指针在一次循环中是不变的,绿指针进行移动,滑动窗口呢,就是通过不断调节子数组的起始位置和终止位置,进而得到我们想要的结果我们也可以看成是双指针的一种。
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!
红指针和绿指针之间的距离就是滑动窗口的大小,符合条件的最小窗口大小为2,其实也很好理解这个思想,就是当红绿之间的和符合条件时,就移动红指针判断是否仍符合条件,不符合就移动绿指针,并记录最小的子长度,直到绿指针移动到最后。
时间复杂度O(n),空间复杂度O(1)

题目代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int chiledlen = Integer.MAX_VALUE;//子数组长度
        int winlen = 0;//窗口大小
        int sum = 0;
        int i = 0;//起始长度位置
        for(int j = 0 ; j < nums.length;j++){
              sum += nums[j];
              //发现符合条件的情况
              while(sum>=s){
                  winlen = j-i+1;//窗口大小
                  chiledlen = Math.min(chiledlen,winlen);
                  //下面两行是滑动窗口的意义所在,改变起点位置,判断是否仍符合条件
                  sum-=nums[i];
                  i++;
              }

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

总结

这个题目是非常好的一个题,大家可以自己做一下,算是初探滑动窗口,大家有更好的方法可以评论讨论啊。

更多题目总结请扫描下面二维码,一块刷题呀。

【leetcode】袁厨每日精选题详解之啥是滑动窗口?该咋用呀!

作者:LeetCode
链接:https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


喜欢 (0)