LeetCode 取经之路——第三题-无重复长度的最长子串
🎉🎉🎉今天给大家分享的是一道滑动窗口的OJ题。
😛😛😛希望我的文章能对你有所帮助，有不足的地方还请各位看官多多指教，大家一起学习交流！
动动你们发财的小手，点点关注点点赞！在此谢过啦！哈哈哈！😛😛😛
目录
?
一、题目解析?
这个题目的意思就是: 在给定的字符串里面，找出不重复的字符串的最大长度。
首先想到的肯定是暴力枚举了，即枚举出所有不重复的字符串，然后找出其中长度最大的。这个还是比较容易想到的。如下图所示：从字符串首元素开始枚举，不重复就一直遍历，直到发现有重复元素为止。但是我们看图是肯定知道有重复，但是代码要怎么写呢？这里就需要用到数据结构中的哈希表了，我的思路是：遍历到一个字符就把它放到哈希表里面，然后再取判断当前这个字符的个数是否大于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;
}
}
?好啦，今天的分享就到这里！
🎉希望各位看官读完文章后，能够有所提升。
?创作不易，还希望各位大佬支持一下！
👍点赞，你的认可是我创作的动力！
?收藏，你的青睐是我努力的方向！
??评论：你的意见是我进步的财富！
?
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！