今天看到一個(gè)非常牛逼的算法, 激動(dòng)得睡不著覺(jué), 趁著腦子還有余熱能理解過(guò)程, 趕緊寫(xiě)下來(lái).
原題
鏈接: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
算法
初見(jiàn)題目相信很多人都想到了滑動(dòng)窗口解法, 然而下面的算法更為精妙
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128];
int ans = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
j = Math.max(index[s.charAt(i)], j);
ans = Math.max(i - j + 1, ans);
index[s.charAt(i)] = i + 1;
}
return ans;
}
僅僅不到 10 行的核心代碼, 執(zhí)行效率超過(guò) 100% , 內(nèi)存利用率也超過(guò)將近 90% 的提交!
解析
先來(lái)點(diǎn)注釋, 簡(jiǎn)單點(diǎn)明下每步的含義
注: 次序, 即索引+1 的值, 表示出現(xiàn)在第幾次, 次序 1 表示第一次, 次序 2 表示第二次, 以此類(lèi)推, 與索引道理相同. 引入次序的概念在 debug 看原理時(shí)會(huì)清晰不少
public int lengthOfLongestSubstring(String s) {
int[] index = new int[128]; // ASCII 占位表又來(lái)了
int ans = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
// 2. j 記錄不重復(fù)字符的最大起點(diǎn)的次序
j = Math.max(index[s.charAt(i)], j);
// 3. i + 1 是當(dāng)前字符出現(xiàn)的次序, 與上述 j 相減就是這次循環(huán)中不重復(fù)字符的最大間隔
ans = Math.max(i + 1 - j, ans);
// 1. 把當(dāng)前字符的本次出現(xiàn)的次序記錄到占位表中
index[s.charAt(i)] = i + 1;
}
return ans;
}
思考記錄
為了方便表示, s 的第 i 個(gè)字符姑且記為 s[i]
- 此算法的核心在于利用 ASCII 碼表記錄每一個(gè)字符的最后出現(xiàn)次序
- 循環(huán)中的三句代碼的邏輯順序其實(shí)是 2, 3, 1, 已在注釋中標(biāo)明
- j 有兩個(gè)含義
- 當(dāng)
index[s.charAt(i)]比較大時(shí), 表示了迄今為止 s[i] 最后一次出現(xiàn)的次序(串中的第幾個(gè)字符, 即索引+1), 0 表示之前沒(méi)有出現(xiàn)過(guò)(巧妙利用了數(shù)組初始值為 0 的特性) - 當(dāng)上個(gè)循環(huán)的
j比較大時(shí), 表示的是之前出現(xiàn)過(guò)的連續(xù)重復(fù)字符的倒數(shù)第二個(gè)字符的次序, 即若 aab 字符串, 當(dāng)前循環(huán)到 b , 表達(dá)式的 j 表示第一個(gè) a 的次序 - 這兩者的共同含義就是不重復(fù)字符的最大起點(diǎn)次序
- 當(dāng)
- ans 就是最大不重復(fù)子串的長(zhǎng)度
-
index[s.charAt(i)] = i + 1最后一步是將當(dāng)前字符出現(xiàn)次序更新到占位表, 以供下個(gè)循環(huán)的 j 使用
語(yǔ)言表達(dá)的內(nèi)容是非常有限的, 要真正搞懂一定要?jiǎng)邮謫尾秸{(diào)試
