友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is"wke", with the length of 3. Note that the answer must be a substring,"pwke"is a subsequence and not a substring.
思路分析
滑动窗口
-
一刷
-
二刷
-
三刷
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* Runtime: 6 ms, faster than 85.45% of Java online submissions for Longest Substring Without Repeating Characters.
*
* Memory Usage: 36.4 MB, less than 99.80% of Java online submissions for Longest Substring Without Repeating Characters.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2019-07-11 21:31
*/
public int lengthOfLongestSubstring(String s) {
if (Objects.isNull(s) || s.length() == 0) {
return 0;
}
int result = 0;
int length = s.length();
Map<Character, Integer> charToIndexMap = new HashMap<>(length * 4 / 3);
for (int i = 0, j = 0; j < length; j++) {
char aChar = s.charAt(j);
if (charToIndexMap.containsKey(aChar)) {
// 这里，如果存在重复的，则从上一个重复字符的下一个字符开始计算。
Integer index = charToIndexMap.get(aChar);
if (index + 1 > i) {
i = index + 1;
}
}
charToIndexMap.put(aChar, j);
if (j - i + 1 > result) {
result = j - i + 1;
}
}
return result;
}
/**
* Runtime: 9 ms, faster than 49.55% of Java online submissions for Longest Substring Without Repeating Characters.
*
* Memory Usage: 36 MB, less than 99.88% of Java online submissions for Longest Substring Without Repeating Characters.
*/
public int lengthOfLongestSubstringWithSlidingWindow(String s) {
if (Objects.isNull(s) || s.length() == 0) {
return 0;
}
int result = 0;
int length = s.length();
int head = 0;
int tail = 0;
Set<Character> characters = new HashSet<>(length * 4 / 3);
while (head < length && tail < length) {
if (!characters.contains(s.charAt(tail))) {
characters.add(s.charAt(tail));
tail++;
if (result < tail - head) {
result = tail - head;
}
} else {
characters.remove(s.charAt(head));
head++;
}
}
return result;
}
/**
* Runtime: 221 ms, faster than 5.02% of Java online submissions for Longest Substring Without Repeating Characters.
*
* Memory Usage: 37.3 MB, less than 97.43% of Java online submissions for Longest Substring Without Repeating Characters.
*/
public int lengthOfLongestSubstringWithBruteForce(String s) {
if (Objects.isNull(s) || s.length() == 0) {
return 0;
}
char[] chars = s.toCharArray();
int result = 0;
for (int i = 0; i < chars.length; i++) {
Set<Character> characters = new HashSet<>(chars.length * 4 / 3);
for (int j = i; j < chars.length; j++) {
char aChar = chars[j];
if (characters.contains(aChar)) {
break;
} else {
characters.add(aChar);
}
}
if (characters.size() > result) {
result = characters.size();
}
}
return result;
}
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
/**
* 有思路，写不出代码
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 19:27:43
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
int result = Integer.MIN_VALUE;
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()) {
char rc = s.charAt(right);
right++;
window.put(rc, window.getOrDefault(rc, 0) + 1);
while (window.get(rc) > 1) {
char lc = s.charAt(left);
left++;
window.put(lc, window.getOrDefault(lc, 0) - 1);
}
result = Math.max(result, right - left);
}
return result == Integer.MAX_VALUE ? 0 : result;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-21 20:41:51
*/
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int result = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
int cnt = map.getOrDefault(c, 0);
if (cnt == 0) {
map.put(c, 1);
result = Math.max(result, right - left + 1);
} else {
map.put(c, cnt + 1);
}
while (map.get(c) > 1) {
char lc = s.charAt(left);
left++;
map.put(lc, map.get(lc) - 1);
}
}
return result;
}