「リートコード - 3. 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
int n = s.length();
if (n == 0 || n == 1) {
return n;
}
HashMap<Character, Boolean> have = new HashMap<Character, Boolean>();
for (int i = 0; i < n; ++i) {
have.put(s.charAt(i), false);
}
int u = 0, v = 0;
have.put(s.charAt(0), true);
while (v + 1 < n && !have.get(s.charAt(v + 1))) {
++v;
have.put(s.charAt(v), true);
}
int res = v + 1;
boolean test = false;
while (v < n - 1) {
++v;
while (!have.get(s.charAt(v)) && v + 1 < n) {
have.put(s.charAt(v), true);
++v;
}
res = Math.max(res, v - u);
if (test) {
System.out.println(res + ", " + u + ", " + v);
}
if (v == n - 1 && !have.get(s.charAt(v))) {
res = Math.max(res, v - u + 1);
if (test) {
System.out.println(res + ", " + u + ", " + v);
}
break;
}
while(s.charAt(u) != s.charAt(v)) {
have.put(s.charAt(u), false);
++u;
}
++u;
res = Math.max(res, v - u + 1);
if (test) {
System.out.println(res + ", " + u + ", " + v);
}
}
return res;
}
}

其实写的时候已经意识到是很累赘的写法了,看了题解其实可以很轻松解决,不过考虑本来复杂度肯定最优还是写完了,然后学习一波。