原題:https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Description
找到?jīng)]有重復(fù)的最長(zhǎng)子串(substring)寿谴。比如pwwkew結(jié)果就是wke嘉裤。這題乍一看上去這樣想，雙重循環(huán)柔袁，外層從頭開(kāi)始掃描唧喉，讀取一個(gè)字母就在已經(jīng)讀到的子串里找有沒(méi)有重復(fù)的捣卤，有就返回。然后把最長(zhǎng)的記錄下來(lái)八孝。這個(gè)brute force我寫了半天沒(méi)寫出來(lái)董朝。。
好的方法是窗口法干跛。維護(hù)兩個(gè)窗口益涧，一個(gè)在前面走一個(gè)在后面走，runner先走驯鳖，走一步就檢查一下現(xiàn)有的hashSet里面有沒(méi)有當(dāng)前的位置的char（contains的復(fù)雜度是O(1)闲询，只有在hash沖突的時(shí)候才會(huì)稍微遍歷一下子，具體看之前我發(fā)的effective java里的hashmap原理）浅辙，set里沒(méi)有就繼續(xù)右移扭弧，有的話，walker開(kāi)始右移记舆，移動(dòng)到跟runner指向的char不同為止鸽捻。
窗口法是string類型題目常有的套路。
已犯錯(cuò)誤：
- walker移動(dòng)到跟runner相同之后runner沒(méi)有右移一位。
- return的應(yīng)該是Math.max(maxLen,runner-walker);
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
int runner = 0, walker = 0;
int maxLen = 0;
HashSet<Character> set = new HashSet<>();
while (runner < s.length()) {
if (!set.contains(s.charAt(runner))) {
set.add(s.charAt(runner));
runner++;
} else {
if (runner - walker > maxLen) maxLen = runner - walker;
while (s.charAt(runner) != s.charAt(walker)) {
set.remove(s.charAt(walker));
walker++;
}
// 分別再走一步
walker++;
runner++;
}
}
return Math.max(maxLen,runner-walker);
}
還有一種奇淫巧技是利用char的value當(dāng)做index御蒲，然后hash：
http://blog.csdn.net/likecool21/article/details/10858799
reference:
http://blog.csdn.net/linhuanmars/article/details/19949159
