題目描述
找出一個(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;
}