网站(网店)建设方案范文,北京网站搭建服务,建个视频网站多少钱,手机端网站设计制作案例#x1f389;#x1f389;#x1f389;今天给大家分享的是一道滑动窗口的OJ题。 3.无重复长度的最长子串 #x1f61b;#x1f61b;#x1f61b;希望我的文章能对你有所帮助#xff0c;有不足的地方还请各位看官多多指教#xff0c;大家一起学习交流#xff01; 动动… 今天给大家分享的是一道滑动窗口的OJ题。 3.无重复长度的最长子串 希望我的文章能对你有所帮助有不足的地方还请各位看官多多指教大家一起学习交流 动动你们发财的小手点点关注点点赞在此谢过啦哈哈哈 目录
一、题目解析
二、源代码 一、题目解析 这个题目的意思就是: 在给定的字符串里面找出不重复的字符串的最大长度。
首先想到的肯定是暴力枚举了即枚举出所有不重复的字符串然后找出其中长度最大的。这个还是比较容易想到的。如下图所示从字符串首元素开始枚举不重复就一直遍历直到发现有重复元素为止。但是我们看图是肯定知道有重复但是代码要怎么写呢这里就需要用到数据结构中的哈希表了我的思路是遍历到一个字符就把它放到哈希表里面然后再取判断当前这个字符的个数是否大于1如果大于那就保存当前的字符串长度继续枚举下一个字符。 其次不知道大家看了上图后会不会很容易的想到 滑动窗口 。上面的解法时间复杂度是O(N^2)相对来说还是比较高的我们可以用 滑动窗口的思想来解决问题:
同样也是需要用到哈希表但是这里我们把字符串转成字符数组后通过字符ASCII码值也可以判断当前字符个数因为相同的字符ASCII码值肯定相同所以在哈希数组里存储的位置也肯定是一样的。因此不必使用真正的 哈希表。大致思路如下
定义两个指针 left 和 right初始时都从 0 开始。right 位置的字符存哈希表再去判断当前字符的个数是否大于1如果大于1那就让 left 位置的字符出窗口然后 left直到当前字符个数为1为止。 每次判断完更新一下字符串的长度即可。最后返回更新的字符串的长度。 这种解法我们不必每次发现重复的字符都要从当前字符的下一个开始遍历这样的遍历方法最后依然会碰到那个重复的字符比如
当前 right 位置发现重复字符a 如果此时从 left 的下一个位置遍历 那么无论如何仍然会碰到那个重复字符a: 所以干脆当我们遇到重复字符的时候更新字符串长度然后直接让 left 跳过这个重复字符即可。 此时 right 也不用回退回去找 left 去了。
下面的大致的一个执行流程 二、源代码
class Solution {public int lengthOfLongestSubstring(String s) {int hash[] new int[128];char str[] s.toCharArray();int ret 0;int left 0;int right 0;int n str.length;while (right n){hash[str[right]];while (hash[str[right]] 1){hash[str[left]]--;//发现重复字符,出窗口left;}ret Math.max(ret,right - left 1);right;}return ret;}
} ✨好啦今天的分享就到这里 希望各位看官读完文章后能够有所提升。 ✨创作不易还希望各位大佬支持一下 点赞你的认可是我创作的动力 ⭐收藏你的青睐是我努力的方向 ✏️评论你的意见是我进步的财富
