LeetCode3 无重复字符的最长子串
程序员文章站
2022-04-04 09:59:43
...
题目 LeetCode3:无重复的最长子串
解法:
(1)线性法:
class Solution {
public int lengthOfLongestSubstring(String s) {
// 定义一个哈希集合 set,初始化结果 max 为 0
Set<Character> set = new HashSet<>();
int max=0;
/* 用快慢指针 i 和 j 扫描一遍字符串,如果快指针所指向的字符已经出现在哈希集合里,
不断地尝试将慢指针所指向的字符从哈希集合里删除
*/
for(int i=0,j=0; j<s.length();j++ ){
while(set.contains(s.charAt(j))){
set.remove(s.charAt(i));
i++;
}
// 当快指针的字符加入到哈希集合后,更新一下结果 max
set.add(s.charAt(j));
max = Math.max(max,set.size());
}
return max;
}
}
改进后的解法:
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int max = 0;
// 用快慢指针 i 和 j 扫描一遍字符串,若快指针所对应的字符已经出现过,则慢指针跳跃
for( int i =0,j=0;j<s.length();j++){
if(map.containsKey(s.charAt(j))){
i = Math.max(i,map.get(s.charAt(j)) +1);
}
map.put(s.charAt(j),j);
max = Math.max(max,j-i+1);
}
return max;
}
}
下一篇: leetCode3:无重复字符的最长子串