思路:
哈希表+双指针
相当于滑动窗口,用哈希表来记录下标,改变左指针的位置
代码:
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map=new HashMap<>();
int i=-1,res=0;
//最开始只创建i
//j用做循环
//j一直往后遍历,i随着出现重复字符而移动
for(int j=0;j<s.length();j++){
if(map.containsKey(s.charAt(j))){
//防止回滚
i=Math.max(i,map.get(s.charAt(j)));
}
map.put(s.charAt(j),j);
//很妙,如果是不重复的,j-i就会比res大
//如果出现冲入,j-i就会比res小
//并且此时j-i就会是在重复元素的右边
res=Math.max(res,j-i);
}
return res;
}
}
分解:
1)j一直往后遍历,i在碰到重复字符时才改变位置到重复字符的右边
2)这条语句是防止回滚,可能前面也出现了重复的,防止i倒回去
i=Math.max(i,map.get(s.charAt(j)));
3)如果是不重复的,j-i就会比res大
如果出现重复,j-i就会比res小
并且此时j-i就会是在重复元素的右边
res=Math.max(res,j-i);
复杂度分析:
时间复杂度:O(N) 循环遍历N个字符
空间复杂度:O(1)字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。
(存储字符时,与存储字符串不一样)