抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

暴力求解

复杂度分析

时间复杂度O(n^2)
空间复杂度O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
for(int i = 0; i < s.length(); i++) {
Set<Character> set = new HashSet<>();
for(int j = i; j < s.length(); j++) {
if(set.contains(s.charAt(j))) break;
res = Math.max(res, j - i + 1);
set.add(s.charAt(j));
}
}
return res;
}
}

滑动窗口

复杂度分析

时间复杂度O(n)
空间复杂度O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int right = -1, ans = 0;
for(int i = 0; i < s.length(); i++) {
if(i != 0) set.remove(s.charAt(i - 1));
while(right + 1 < s.length() && !set.contains(s.charAt(right + 1))) {
set.add(s.charAt(right + 1));
++right;
}

ans = Math.max(ans, right - i + 1);

}

return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals("")) return 0;
int start = 0, end = 0;
int max = 1;
HashSet<Character> set = new HashSet<>();
while(end < s.length()) {
char c_e = s.charAt(end);
if(set.contains(c_e)) {
set.remove(s.charAt(start));
start++;
} else {
set.add(c_e);
end++;
max = Math.max(max, set.size());
}
}
return max;
}
}
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
public int lengthOfLongestSubstring(String s) {
int length = s.length();
if (length < 2) return length;

//双指针,将遇到的字符放进Map,看是不是重复的。
Map<Character, Integer> map = new HashMap<>();
char[] array = s.toCharArray();
int size = 0;

//窗口左指针
int left = 0;

for (int right = 0; right < length; right++) {
//i是右指针
if (map.containsKey(array[right])) {
//如果包含了此元素,说明重复,需要移动左指针
//窗口不能回退。
left = Math.max(map.get(array[right]) + 1, left);
}
//修改当前元素索引
map.put(array[right], right);
//计算长度
size = Math.max(size, right - left + 1);
}
return size;
}

用户交流区

温馨提示: 遵纪守法, 友善评论!





津ICP备19009605号

WordCount24k