題目
解題方案
思路 1: 暴力解法, 雙重循環(huán)遍歷
簡(jiǎn)單粗暴些, 找一個(gè)最長(zhǎng)子串, 那么我們用兩個(gè)循環(huán) ** 窮舉所有子串 **, 然后再用一個(gè)函數(shù)判斷該子串中有沒(méi)有重復(fù)的字符仇冯。
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0; // 保存當(dāng)前得到滿足條件的子串的最大值
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++) // 之所以 j<= n, 是因?yàn)槲覀冏哟?[i, j), 左閉右開(kāi)
if (allUnique(s, i, j)) ans = Math.max(ans, j - i); // 更新 ans
return ans;
}
public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>(); // 初始化 hash set
for (int i = start; i < end; i++) { // 遍歷每個(gè)字符
Character ch = s.charAt(i);
if (set.contains(ch)) return false; // 判斷字符在不在 set 中
set.add(ch); // 不在的話將該字符添加到 set 里邊
}
return true;
}
時(shí)間復(fù)雜度：兩個(gè)循環(huán), 加上判斷子串滿足不滿足條件的函數(shù)中的循環(huán), 。
空間復(fù)雜度：使用了一個(gè) set, 判斷子串中有沒(méi)有重復(fù)的字符翰舌。由于 set 中沒(méi)有重復(fù)的字符, 所以最長(zhǎng)就是整個(gè)字符集, 假設(shè)字符集的大小為 m, 那么 set 最長(zhǎng)就是 m 坏挠。另一方面, 如果字符串的長(zhǎng)度小于 m, 是 n 奴愉。那么 set 最長(zhǎng)也就是 n 了冒晰。綜上, 空間復(fù)雜度為 廷没。
思路二：滑動(dòng)窗口
遺憾的是上邊的算法沒(méi)有通過(guò) leetCode, 時(shí)間復(fù)雜度太大, 造成了超時(shí)朝氓。我們?cè)趺磥?lái)優(yōu)化一下呢宪彩？
上邊的算法中, 我們假設(shè)當(dāng) i 取 0 的時(shí)候,
j 取 1, 判斷字符串 str [0, 1) 中有沒(méi)有重復(fù)的字符休讳。
j 取 2, 判斷字符串 str [0, 2) 中有沒(méi)有重復(fù)的字符。
j 取 3, 判斷字符串 str [0, 3) 中有沒(méi)有重復(fù)的字符毯焕。
j 取 4, 判斷字符串 str [0, 4) 中有沒(méi)有重復(fù)的字符衍腥。
做了很多重復(fù)的工作, 因?yàn)槿绻?str [0, 3) 中沒(méi)有重復(fù)的字符, 我們不需要再判斷整個(gè)字符串 str [0, 4) 中有沒(méi)有重復(fù)的字符, 而只需要判斷 str [3] 在不在 str [0, 3) 中, 不在的話, 就表明 str [0, 4) 中沒(méi)有重復(fù)的字符。
如果在的話, 那么 str [0, 5), str [0, 6), str [0, 7) 一定有重復(fù)的字符, 所以此時(shí)后邊的 j 也不需要繼續(xù)增加了纳猫。i++ 進(jìn)入下次的循環(huán)就可以了婆咸。
此外, 我們的 j 也不需要取 i + 1, 而只需要從當(dāng)前的 j 開(kāi)始就可以了。
綜上, 其實(shí)整個(gè)關(guān)于 j 的循環(huán)我們完全可以去掉了, 此時(shí)可以理解變成了一個(gè)「滑動(dòng)窗口」芜辕。
判斷一個(gè)字符在不在字符串中, 我們需要可以遍歷整個(gè)字符串, 遍歷需要的時(shí)間復(fù)雜度就是 , 加上最外層的 i 的循環(huán), 總體復(fù)雜度就是
尚骄。我們可以繼續(xù)優(yōu)化, 判斷字符在不在一個(gè)字符串, 我們可以將已有的字符串存到 Hash 里, 這樣的時(shí)間復(fù)雜度是
, 總的時(shí)間復(fù)雜度就變成了
。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
時(shí)間復(fù)雜度：在最壞的情況下, while 循環(huán)中的語(yǔ)句會(huì)執(zhí)行 2n 次, 例如 abcdefgg, 開(kāi)始的時(shí)候 j 一直后移直到到達(dá)第二個(gè) g 的時(shí)候固定不變, 然后 i 開(kāi)始一直后移直到 n, 所以總共執(zhí)行了 2n 次, 時(shí)間復(fù)雜度為 侵续。
空間復(fù)雜度：和上邊的類似, 需要一個(gè) Hash 保存子串, 所以是 倔丈。
思路三：跳躍窗口
繼續(xù)優(yōu)化, 我們看上邊的算法的一種情況。
當(dāng) j 指向的 c 存在于前邊的子串 abcd 中, 此時(shí) i 向前移到 b, 此時(shí)子串中仍然含有 c, 還得繼續(xù)移動(dòng), 所以這里其實(shí)可以優(yōu)化状蜗。我們可以一步到位, 直接移動(dòng)到子串 c 的位置的下一位需五！
實(shí)現(xiàn)這樣的話, 我們將 set 改為 map, 將字符存為 key, 將對(duì)應(yīng)的下標(biāo)存到 value 里就實(shí)現(xiàn)了。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1); // 下標(biāo) + 1 代表 i 要移動(dòng)的下個(gè)位置
}
return ans;
}
}
與解法二相比
由于采取了 i 跳躍的形式, 所以 map 之前存的字符沒(méi)有進(jìn)行 remove, 所以 if 語(yǔ)句中進(jìn)行了 Math.max(map.get(s.charAt(j)), i), 要確認(rèn)得到的下標(biāo)不是 i 前邊的轧坎。
還有個(gè)不同之處是 j 每次循環(huán)都進(jìn)行了自加 1, 因?yàn)?i 的跳躍已經(jīng)保證了 str [i, j] 內(nèi)沒(méi)有重復(fù)的字符串, 所以 j 直接可以加 1 宏邮。而解法二中, 要保持 j 的位置不變, 因?yàn)椴恢篮?j 重復(fù)的字符在哪個(gè)位置。
最后個(gè)不同之處是, ans 在每次循環(huán)中都進(jìn)行更新, 因?yàn)?ans 更新前 i 都進(jìn)行了更新, 已經(jīng)保證了當(dāng)前的子串符合條件, 所以可以更新 ans 。而解法二中, 只有當(dāng)當(dāng)前的子串不包含當(dāng)前的字符時(shí), 才進(jìn)行更新蜜氨。
時(shí)間復(fù)雜度：我們將 2n 優(yōu)化到了 n, 但最終還是和之前一樣, 械筛。
空間復(fù)雜度：也是一樣的, 。
思路四：使用數(shù)組
和解法三思路一樣, 區(qū)別的地方在于, 我們不用 Hash, 而是直接用數(shù)組, 字符的 ASCII 碼值作為數(shù)組的下標(biāo), 數(shù)組存儲(chǔ)該字符所在字符串的位置飒炎。適用于字符集比較小的情況, 因?yàn)槲覀儠?huì)直接開(kāi)辟和字符集等大的數(shù)組埋哟。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128];
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1; // (下標(biāo) + 1) 代表 i 要移動(dòng)的下個(gè)位置
}
return ans;
}
}
和解法 3 不同的地方在于, 沒(méi)有了 if 的判斷, 因?yàn)槿绻?index [s.charAt(j)] 不存在的話, 它的值會(huì)是 0, 對(duì)最終結(jié)果不會(huì)影響。
時(shí)間復(fù)雜度：郎汪。
空間復(fù)雜度：, m 代表字符集的大小赤赊。這次不論原字符串多小, 都會(huì)利用這么大的空間。
總結(jié)
綜上, 我們一步一步的尋求可優(yōu)化的地方, 對(duì)算法進(jìn)行了優(yōu)化怒竿。又加深了 Hash 的應(yīng)用, 以及利用數(shù)組巧妙的實(shí)現(xiàn)了 Hash 的作用砍鸠。
