网站内容建设出现的问题,设计公司宣传文案,怎样进入谷歌网站,深圳建设网站top028文章目录 前言一、长度最小子数组1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: #x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 #x1f4d7; Java数据结构: 顺序表, 链… 文章目录 前言一、长度最小子数组1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新) 一、长度最小子数组
1, 题目
OJ链接
一般来说, 如果我们研究的对象是 “连续的区间” 就可以考虑滑动窗口 滑动窗口其实就是同向双指针, 滑动窗口的特点是, 前后两个指针不会回退, 并且窗口总是向前滑动, 窗口不是固定大小的, 可能边长也可能变短, 如果你在分析题目的时候发现了这些特征, 那就基本是滑动窗口的解法了 2, 思路分析
暴力解法 : 两层 for 循环, 先固定第一个字符, 然后遍历第二个字符, 每遍历到一个字符就判断是否已经出现过, 利用暴力枚举, 寻找出所有子序列
但这一定会超时, 有没有优化的方案呢?
1, 使用哈希表, 定义一个 set, 用于检查当前字符是否已经出现过2 , 定义 maxLen, 用于记录目前最大长度3, 定义 left 和 right 指针, 初始位置都从0开始, left 用于标记子序列的左边界, right 用于标记子序列的右边界
前期依然是暴力枚举找到第一个满足条件的子数组, 但接下来就不需要接着暴力枚举, 如图所示 增大窗口对应的操作就是 right, 缩小窗口的操作就是 left
right 每指向一个字符, 就判断是否已经存在
如果不存在, 直接增大窗口即可如果已经存在, 就 要找到 窗口中的这个已出现的字符, 并将它排除在窗口之外 需要注意的是, 要找到 窗口中的这个已出现的字符 这个操作是一个循环, 但上图中没有表现出来, 如下图所示 综上所述, 可以发现, left 和 right 指针全程没有回退, 并且窗口即会边长也会变短, 但一直在向前滑动, 这就是滑动窗口的特性 3, 代码 public int lengthOfLongestSubstring(String s) {SetCharacter set new HashSet();int left 0;int right 0;int maxLen 0;while(right s.length()){char ch s.charAt(right);if(set.contains(ch) ){while(s.charAt(left) ! ch) {set.remove(s.charAt(left));left;}left;}set.add(ch);maxLen Math.max(maxLen, right - left 1);right;}return maxLen;}
