Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你:
📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)

一、长度最小子数组

1, 题目

OJ链接

一般来说, 如果我们研究的对象是 “连续的区间” 就可以考虑滑动窗口

滑动窗口其实就是"同向双指针", 滑动窗口的特点是, 前后两个指针不会回退, 并且窗口总是向前滑动, 窗口不是固定大小的, 可能边长也可能变短, 如果你在分析题目的时候发现了这些特征, 那就基本是滑动窗口的解法了

2, 思路分析

暴力解法 : 两层 for 循环, 先固定第一个数, 然后遍历第二个数, 每一个子数组都计算总和以及长度, 利用暴力枚举, 寻找出所有子数组

但这一定会超时, 有没有优化的方案呢?

1, 定义 sum, 记录子数组的和, 用于和 target 比大小
2 , 定义 minLength, 记录目前最小的长度
3, 定义 left 和 right 指针, 初始位置都从0开始, left 用于标记子数组的左边界, right 用于标记子数组的右边界

前期依然是暴力枚举找到第一个满足条件的子数组, 但接下来就不需要接着暴力枚举, 因为题目给定数组中所有元素都是整数, 利用这一单调性, 做第一步优化, 如图所示

一旦窗口(子数组)中的值大于 target 了, 就判断是否为目前最短的子数组, 后续没有必要再让 right++ 增大窗口了, 因为后面的数一定是整数, target 一定会变大的同时, 长度也一定增大, 我们要求最小连续子数组, 所以直接排除后面的情况 !

我们要做的是让 left++, 缩小窗口, 尽量获取到更短的子数组

如果缩小窗口后, 总和仍然大于 target, 就继续缩小窗口
否则继续让 right++, 增大窗口, 寻找总和大于 target 的子数组

此处可以做第二步优化, left++之后, right 指针需要回退, 一步一步计算窗口中的总和吗? 不需要, 因为刚才 right 已经走过一次了, 直接让当前的 sum 减去刚才 left 的值即可

增大窗口对应的操作就是 right++, 缩小窗口的操作就是 left++

Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码,OJ题,java,leetcode,滑动窗口,双指针

在上述过程中, 一旦窗口总和大于 target 了, 就会更新变量 minLenth, 然后缩小窗口, 注意, 缩小窗口也是一个循环, 因为我们要尽量找到最短的连续子数组

综上所述, 可以发现, left 和 right 指针全程没有回退, 并且窗口即会边长也会变短, 但一直在向前滑动, 这就是滑动窗口的特性文章来源地址https://www.toymoban.com/news/detail-682236.html

3, 代码

	public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        while(right < nums.length){
            sum += nums[right];
            while(sum >= target)  {
                // left位置不变时, right没有必要往后遍历
                // 先要让left++
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        // 还要判断如果没有一个满足条件的子数组, 要返回0
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }