无重复字符的最长子串

无重复字符的最长子串

题目描述

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

示例

示例 1:

1
2
3
输入:"abcabcbb"
输出:3
解释:因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入:"bbbbb"
输出:1
解释:因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
输入:"pwwkew"
输出:3
解释:因为无重复字符的最长子串是 "wke",所以其长度为 3。

限制

请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一

这题我一开始用到的是比较暴力的方法,直接取出所有的子串,再判断每个子串中是否含有重复字符,并记录最长的不含重复字符的子串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.HashMap;
import java.util.Map;

class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length() + 1; j++) {
String sub = s.substring(i, j);
if (this.check(sub)) {
max = Math.max(max, sub.length());
} else {
break;
}
}
}
return max;
}

public boolean check(String str) {
Map<Character, Character> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
Character ret = map.put(ch, ch);
if (ret != null) {
return false;
}
}
return true;
}
}

不出意料,这种解法直接超时了。

解法二

解法二是我对解法一的一点点优化。在第二层循环中移动右指针时,如果遇到了重复的字符就直接结束该层循环,将左指针右移一位,开始下一次循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.HashMap;
import java.util.Map;

class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); i++) {
Map<Character, Character> map = new HashMap<>();
for (int j = i; j < s.length(); j++) {
Character c = s.charAt(j);
Character ch = map.put(c, c);
if (ch != null) {
max = Math.max(max, j - i);
break;
}
}
}
return max;
}
}

优化一些后的解法以 110 ms 的成绩通过了测试,但是和优秀题解还是有不小的差距。

解法三

我看了一下官方的题解,官方采用了一种叫滑动窗口的方法。我发现在题解二中的优化还不够充分,没有利用到上一次外层循环中的判重结果,参考官方题解后重新写出以下解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashSet;
import java.util.Set;

public class Solution {
public int lengthOfLongestSubstring(String s) {
int left;
int right = 0;
int ans = 0;
Set<Character> set = new HashSet<>();
Character ch;
for (left = 0; left < s.length(); left++) {
while (right < s.length()) {
ch = s.charAt(right);
if (set.contains(ch)) break;
set.add(ch);
right++;
}
ans = Math.max(right - left, ans);
set.remove(s.charAt(left));
}
return ans;
}
}

这种解法的时间直接降到了 8 ms。