相信看了這個(gè)標(biāo)題的同學(xué)，對(duì)這道題以已經(jīng)非常不陌生了，就是leecode當(dāng)中的第三題，之所以要單獨(dú)的寫一寫主要對(duì)我來說，里面涉及到有一個(gè)滑動(dòng)窗口, 散列表， 字符編碼等知識(shí)點(diǎn)比較重要，也有幾個(gè)小技巧，這里我也權(quán)當(dāng)記憶鞏固了，這道題也曾被Micosoft, Amazon, Bloomberg, Airbnb, Adobe作為經(jīng)典面試題，包括限流, TCP擁塞都有使用到滑動(dòng)窗口思想。
題目
給給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。示例 1: 輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
舉例：
作為大多數(shù)人，找出如圖的不相同字符的最大長(zhǎng)度，基本上判斷3次，ABC長(zhǎng)度為3，BCAD長(zhǎng)度為4，CADC長(zhǎng)度為3，判斷到這里直接就可以給出答案了，就是4，因?yàn)镃ADC已經(jīng)到字符串末尾了，不用再比較了。但是讓程序去實(shí)現(xiàn)這個(gè)功能就要設(shè)計(jì)一下了。
根據(jù)事例提出幾個(gè)問題：
①在第一輪判定了ABC都不重復(fù)，我們?cè)趺磳?shí)現(xiàn)將BC作為一個(gè)整體第二輪就不需要要判斷BC是不重復(fù)的子串?
②如何選取數(shù)據(jù)結(jié)構(gòu)？
<font face="黑體">滑動(dòng)窗口：</font>
顧名思義，滑動(dòng)窗口通常指可以動(dòng)態(tài)擴(kuò)容和縮容的一個(gè)窗口，如"ABCADC“這個(gè)事例，在第二輪我們視BC為一個(gè)整體進(jìn)行擴(kuò)容，擴(kuò)容到BCAD。
如”pwwkew“，在第二輪當(dāng)PW遇到W，我們進(jìn)行縮容，直接從下一個(gè)W開始。如圖所示。通?；瑒?dòng)窗口的實(shí)現(xiàn)需要結(jié)合散列表來實(shí)現(xiàn)來維護(hù)一個(gè)不重復(fù)子串，當(dāng)獲取接下來的字符如果存在在散列表中，指針右移。
散列表：
通常一旦涉及到出現(xiàn)次數(shù)，我們可以用散列表，在Java中我們常用的涉及到散列表的容器有HashMap， HashSet, HashTable等等。這里我們可以選用HashSet,其實(shí)其它幾種都可以實(shí)現(xiàn)。
Set<Character> occ = new HashSet<>(); // 創(chuàng)建一個(gè)散列表
occ.remove(s.charAt(i - 1)); // 指針右移(移除）
occ.add((s.charAt(rk + 1))); // 指針右移(添加)
!occ.contains(s.charAt(rk + 1)) // 判斷接下來的字符是否出現(xiàn)在散列表
參考代碼
public static int lengthOfLongestSubstring(String s) {
// 哈希集合，記錄每個(gè)字符是否出現(xiàn)過
Set<Character> occ = new HashSet<>();
int n = s.length();
// 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒有開始移動(dòng)
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指針向右移動(dòng)一格，移除一個(gè)字符
occ.remove(s.charAt(i - 1));
}
if (ans >= n -i) {
break;
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不斷地移動(dòng)右指針
occ.add((s.charAt(rk + 1)));
++rk;
}
// 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
測(cè)試用例：
@Test
public void islengthOfLongestSubstring() {
// int i = lengthOfLongestSubstring("abcadc");
int i = lengthOfLongestSubstring("pwwkew");
Assert.assertNotNull(i);
}
拓展
public int lengthOfLongestSubstring1(String s) {
if(s==null||s.equals(""))
return 0;
int []map = new int[256];
for(int i=0;i<256;i++)
map[i]=-1;
int len = 0, cur = 0, pre = -1;
for(int i=0;i<s.length();i++){
int x = s.charAt(i);
pre = Math.max(pre,map[x]); // 記錄上次比較出現(xiàn)過得最大值
cur = i - pre; // 指針 - 最大值,當(dāng)指針右移，i變大，他們的差值就越大;出現(xiàn)相同的值，pre變大
len = Math.max(len,cur);
map[x] = i; // 對(duì)出現(xiàn)過的字符賦值為字符串下標(biāo)
}
return len;
}
我們知道，在計(jì)算機(jī)中，所有的數(shù)據(jù)在存儲(chǔ)和運(yùn)算時(shí)都要使用二進(jìn)制數(shù)表示，在英語(yǔ)中，用128個(gè)符號(hào)編碼便可以表示所有，其他語(yǔ)言，128個(gè)符號(hào)是不夠的。一些歐洲國(guó)家決定，利用字節(jié)中閑置的最高位編入新的符號(hào)，這些歐洲國(guó)家使用的編碼體系，可以表示最多256個(gè)符號(hào)。但是漢字多達(dá)10萬(wàn)左右，漢字使用GB2312，理論上可以表示 256 x 256 = 65536 個(gè)符號(hào)。
在本題中主要只涉及到字符串，完全可以使用一個(gè)數(shù)組，容量大小是256，初始長(zhǎng)度都為-1，出現(xiàn)過的值記錄一下，pre比較出現(xiàn)過的值，通過右移指針與pre的差來記錄最近一次最大值，len為歷史最大值。
熱門推薦：
文末福利，最近整理一份面試資料《Java面試通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。獲取方式：GitHub github.com/Tingyu-Notes，更多內(nèi)容關(guān)注我的簡(jiǎn)書，陸續(xù)奉上。
