本文主要是介绍LeetCode 取经之路——第三题-无重复长度的最长子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
🎉🎉🎉今天给大家分享的是一道滑动窗口的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;}
}
✨好啦,今天的分享就到这里!
🎉希望各位看官读完文章后,能够有所提升。
✨创作不易,还希望各位大佬支持一下!
👍点赞,你的认可是我创作的动力!
⭐收藏,你的青睐是我努力的方向!
✏️评论:你的意见是我进步的财富!
这篇关于LeetCode 取经之路——第三题-无重复长度的最长子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!