劍指 Offer 48. 最長不含重複字元的子字元串（中等）

思路：

哈希表+雙指針

相當于滑動視窗，用哈希表來記錄下标，改變左指針的位置

代碼：

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) 大小的額外空間。

（存儲字元時，與存儲字元串不一樣）