第三题：无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
V1版本
最开始想到的就是通过双重for循环依次去匹配，获取最大长度，但想了想这种方式肯定是效率最差的，
于是乎想着用散列表来保存节点出现的位置，然后在去计算最大长度，结果在和种测试用例面前缝缝补补，代码又臭又长，只好先放弃了，先用最暴力的方法解决一下吧，代码如下
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();
// 用于校验是否遇到重复值
Set<Character> set;
// 定义最大长度
int maxLength = 0;
for (int i = 0; i < chars.length; i++) {
// 剩下的总长度比当前获取的最大长度小，则没必要在执行下去了
if (s.length() - 1 < maxLength) {
return maxLength;
}
set = new HashSet<>();
int j = i;
for (; j < s.length(); j++) {
if (!set.add(chars[j])) {
maxLength = Math.max(maxLength, j - i);
break;
}
}
// 没有遇到重复字条跳出的情况
if (j >= s.length()) {
maxLength = Math.max(maxLength, s.length() - i);
}
}
return maxLength;
}
结果也是不出所料，效率太低，继续优化吧
image.png
V2版本
有了V1暴力破解的经验，V1效率太低的原因就是重复的操作太多了，得想办法减少这种不必要的重复工作
想想其实没必要每次都从头开始匹配
例：abcabcbb
第一次匹配到abc 第四个字符了a,重复了，我可以记录一下这时的最大长方度，然后将a去掉，继续用bca往下匹配
这样只需要循环一遍即可得到结果，说干就干，代码如下,利用了队列来保存有效不得复的字符
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();
// 用于校验是否遇到重复值
Set<Character> set = new HashSet<>();
// 队列保存走过的字符
Queue<Character> queue = new LinkedBlockingDeque<>();
// 定义最大长度
int maxLength = 0;
// 当前字符
char curChar;
// 被队列弹出的字符
char pollChar;
for (int i = 0; i < chars.length; i++) {
// 在队列中添加一个元素
curChar = chars[i];
queue.add(curChar);
// 添加到set中，校验是否有重复
if (set.add(curChar)) {
continue;
}
// 有重复字符了，获取当前最在不重复字符长度，由于queue里面有一个重复的字符，计算的时候需要减1
maxLength = Math.max(maxLength, queue.size() - 1);
// 此时需要弹出与队列中与当前字符相同的字符之前的所有字符，包括当前字符
do {
// 弹出并删除头字符
pollChar = queue.poll();
// 头字符和当前字符不一样，将该头符在set集合中删除，并继续执行弹出操作
if (curChar != pollChar) {
set.remove(pollChar);
}
} while (curChar != pollChar);
}
// 有可能存在aab这种没有收尾的情况
return Math.max(maxLength, queue.size());
}
可是执行效率依旧感人，我得去找找大佬们的思路了
image.png
V3版本
参考官方版本，官方版本用的是滑动窗口，简洁太多，根本不需要另外用队列来记录字符
一个map就搞定了，节约不少空间和时间成本，又强又骚，向大牛学习
public int lengthOfLongestSubstring(String s) {
// 定义一个map保存字符与坐标信息
Map<Character, Integer> map = new HashMap<>();
// 最大长度
int maxLength = 0;
int num = s.length();
int start = -1, end = 0;
// 当前字符
char curChar;
for (; end < num; end++) {
curChar = s.charAt(end);
// 校验字符在map中是否存在
if (map.containsKey(curChar)) {
// 已存在，则需要将start向后滑动
start = Math.max(map.get(curChar), start);
}
maxLength = Math.max(maxLength, end - start);
map.put(curChar, end);
}
return maxLength;
}
image.png
网友评论