題目描述
找出一個(gè)字符串中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度挤聘。
示例：
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"侨舆，所以其長(zhǎng)度為 3谈息。
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1巨双。
解析
算法技巧：
應(yīng)用HashMap存儲(chǔ)遍歷的字符及其坐標(biāo)索引噪猾，以減少遍歷字符串次數(shù)，利用空間換取時(shí)間
實(shí)現(xiàn)方法：
方法一：暴力法依次遍歷字符串中每個(gè)字符作為開(kāi)頭的最長(zhǎng)子串筑累，在眾多子串中選出最長(zhǎng)子串袱蜡。
方法二：在方法一基礎(chǔ)上每次查找新的字符開(kāi)頭的子串時(shí)，記錄已經(jīng)存在的字符慢宗，這樣可以消除為判斷是否重復(fù)而往回校驗(yàn)的時(shí)間消耗坪蚁。
方法三：遍歷一趟字符串，并且不走回頭路镜沽。需要記錄子串開(kāi)始的位置head敏晤，和HashMap記錄已經(jīng)存在的字符，如果遇到當(dāng)前字符已經(jīng)存在則統(tǒng)計(jì)當(dāng)前的最長(zhǎng)子串缅茉，head不需要移動(dòng)到1嘴脾，而是移動(dòng)到重復(fù)字符的后一位。例如蔬墩，s[j]在s[i]~s[j-1]存在译打，下標(biāo)為k（i <= k <= j-1 ），則新的子串從k + 1開(kāi)始即可拇颅，因?yàn)閕與k之間開(kāi)頭的字符不可能存在長(zhǎng)度超過(guò)j-i的不重復(fù)子串奏司。同時(shí)，考慮一種特殊情況樟插，如果HashMap中存在當(dāng)前字符韵洋，但是當(dāng)前字符卻不在遍歷的區(qū)間，那么此時(shí)head不需要移動(dòng)黄锤，但是要更新HashMap麻献。
代碼
public int lengthOfLongestSubstring(String s) {
int head = 0, tail = head, longest = 0;
Map<Character, Integer> map = new HashMap<>();
while(tail < s.length()){
char c = s.charAt(tail);
Integer i = map.get(c);
if(i != null){//HashMap存在當(dāng)前字符c
longest = (tail - head) > longest ? (tail - head) : longest;//遇到重復(fù)時(shí)更新最長(zhǎng)子串長(zhǎng)度
head = head > i ? head : i + 1;//判斷是否在當(dāng)前區(qū)間內(nèi)，決定是否改變head
}
map.put(c, tail);//新插入或者更新HashMap
tail++;
}
return (tail - head) > longest ? (tail - head) : longest;
}
