forked from forging2012/JavaArithmetic
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLeetCode3.java
More file actions
82 lines (58 loc) · 2.28 KB
/
LeetCode3.java
File metadata and controls
82 lines (58 loc) · 2.28 KB
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
package LeetCode;
public class LeetCode3 {
//https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
// 滑动窗口
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 整个循环从 l == 0; r == -1 这个空窗口开始
// 到l == s.size(); r == s.size()-1 这个空窗口截止
// 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
while (l < s.length()) {
if (r + 1 < s.length() && freq[s.charAt(r + 1)] == 0)
freq[s.charAt(++r)]++;
else //r已经到头 || freq[s[r+1]] == 1
freq[s.charAt(l++)]--;
res = Math.max(res, r - l + 1);
}
return res;
}
public int lengthOfLongestSubstring2(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 在这里, 循环中止的条件可以是 r + 1 < s.length(), 想想看为什么?
// 感谢课程QQ群 @千千 指出 :)
while( r + 1 < s.length() ){
if( r + 1 < s.length() && freq[s.charAt(r+1)] == 0 )
freq[s.charAt(++r)] ++;
else //freq[s[r+1]] == 1
freq[s.charAt(l++)] --;
res = Math.max(res, r-l+1);
}
return res;
}
// 滑动窗口的另一个实现, 仅做参考
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
public int lengthOfLongestSubstring3(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
while(r + 1 < s.length()){
while(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
freq[s.charAt(++r)] ++;
res = Math.max(res, r - l + 1);
if(r + 1 < s.length()){
freq[s.charAt(++r)] ++;
assert(freq[s.charAt(r)] == 2);
while(l <= r && freq[s.charAt(r)] == 2)
freq[s.charAt(l++)] --;
}
}
return res;
}
}