第三道題如下：
- ** Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.*
思路：如上圖（畫得不好請(qǐng)見(jiàn)諒）儒搭。維護(hù)一個(gè)窗口[walker,runner]：
一、窗口區(qū)間上限runner跑在前面香拉，每掃描一次辽社，將對(duì)應(yīng)的元素添加至HashSet里碉就，直到掃描到HashSet里已經(jīng)存在的元素午阵，runner停下县袱，記為runner1浑娜。等一等走得比較慢的walker。此時(shí)式散，窗口內(nèi)存在與walker處相同的元素筋遭；
二、首先記錄walker與runner的距離暴拄，因?yàn)榇藭r(shí)walker往前的子字符串都是無(wú)元素重復(fù)的漓滔，與max比大小。緊接著乖篷，walker也不能落后响驴，走了起來(lái)，一直到與runner一樣元素的地方撕蔼。邊走邊把之前那些元素從HashSet里丟掉豁鲤，直到找到那個(gè)與runner1元素相同的地方秽誊，記為walker1。walker1前面部分丟掉的原因是不可能找到一個(gè)包含[walker1,runner1]區(qū)間的再大的區(qū)間使得其實(shí)無(wú)重復(fù)的琳骡，因?yàn)閇walker1,runner1]區(qū)間內(nèi)已有重復(fù)元素锅论。所以求下一個(gè)目標(biāo)區(qū)間只能往前走，把下區(qū)間丟掉楣号，此時(shí)去到第三步最易；
三、把walker1前面(包括自身)丟掉后炫狱，問(wèn)題回到了第一步藻懒，重復(fù)第一步的過(guò)程即可。
Java代碼如下：
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null && s.length()==0)
return 0;
HashSet<Character> set = new HashSet<Character>();
int max = 0;
int walker = 0;
int runner = 0;
for(;runner<s.length();runner++)
{
if(set.contains(s.charAt(runner)))
{
max = (runner-walker)>max?(runner-walker):max;
while(s.charAt(walker)!=s.charAt(runner))
{
set.remove(s.charAt(walker));
walker++;
}
walker++;
}
else
{
set.add(s.charAt(runner));
}
}
max = (runner-walker)>max?(runner-walker):max;
return max;
}
}
學(xué)習(xí)參考：
[1]. LeetCode – Longest Substring Without Repeating Characters (Java)
[2]. Repeating Characters -- LeetCode
