題目

無重復(fù)字符的最長子串

解題方案

思路 1: 暴力解法, 雙重循環(huán)遍歷

簡單粗暴些, 找一個(gè)最長子串, 那么我們用兩個(gè)循環(huán) ** 窮舉所有子串 **, 然后再用一個(gè)函數(shù)判斷該子串中有沒有重復(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), 左閉右開
            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, 判斷子串中有沒有重復(fù)的字符。由于 set 中沒有重復(fù)的字符, 所以最長就是整個(gè)字符集, 假設(shè)字符集的大小為 m, 那么 set 最長就是 m 。另一方面, 如果字符串的長度小于 m, 是 n 。那么 set 最長也就是 n 了。綜上, 空間復(fù)雜度為 。

思路二：滑動窗口

遺憾的是上邊的算法沒有通過 leetCode, 時(shí)間復(fù)雜度太大, 造成了超時(shí)。我們怎么來優(yōu)化一下呢？

上邊的算法中, 我們假設(shè)當(dāng) i 取 0 的時(shí)候,

j 取 1, 判斷字符串 str [0, 1) 中有沒有重復(fù)的字符。

j 取 2, 判斷字符串 str [0, 2) 中有沒有重復(fù)的字符。

j 取 3, 判斷字符串 str [0, 3) 中有沒有重復(fù)的字符。

j 取 4, 判斷字符串 str [0, 4) 中有沒有重復(fù)的字符。

做了很多重復(fù)的工作, 因?yàn)槿绻?str [0, 3) 中沒有重復(fù)的字符, 我們不需要再判斷整個(gè)字符串 str [0, 4) 中有沒有重復(fù)的字符, 而只需要判斷 str [3] 在不在 str [0, 3) 中, 不在的話, 就表明 str [0, 4) 中沒有重復(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 開始就可以了。

綜上, 其實(shí)整個(gè)關(guān)于 j 的循環(huán)我們完全可以去掉了, 此時(shí)可以理解變成了一個(gè)「滑動窗口」。

整體就是橘色窗口在依次向右移動

判斷一個(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)中的語句會執(zhí)行 2n 次, 例如 abcdefgg, 開始的時(shí)候 j 一直后移直到到達(dá)第二個(gè) g 的時(shí)候固定不變, 然后 i 開始一直后移直到 n, 所以總共執(zhí)行了 2n 次, 時(shí)間復(fù)雜度為 。

空間復(fù)雜度：和上邊的類似, 需要一個(gè) Hash 保存子串, 所以是 。

思路三：跳躍窗口

繼續(xù)優(yōu)化, 我們看上邊的算法的一種情況。

特殊情況

當(dāng) j 指向的 c 存在于前邊的子串 abcd 中, 此時(shí) i 向前移到 b, 此時(shí)子串中仍然含有 c, 還得繼續(xù)移動, 所以這里其實(shí)可以優(yōu)化。我們可以一步到位, 直接移動到子串 c 的位置的下一位！

直接跳到重復(fù)字符的下一位

實(shí)現(xiàn)這樣的話, 我們將 set 改為 map, 將字符存為 key, 將對應(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 要移動的下個(gè)位置
        }
        return ans;
    }
}

與解法二相比

由于采取了 i 跳躍的形式, 所以 map 之前存的字符沒有進(jìn)行 remove, 所以 if 語句中進(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)沒有重復(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ù)組存儲該字符所在字符串的位置。適用于字符集比較小的情況, 因?yàn)槲覀儠苯娱_辟和字符集等大的數(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 要移動的下個(gè)位置
        }
        return ans;
    }
}

和解法 3 不同的地方在于, 沒有了 if 的判斷, 因?yàn)槿绻?index [s.charAt(j)] 不存在的話, 它的值會是 0, 對最終結(jié)果不會影響。

時(shí)間復(fù)雜度：。

空間復(fù)雜度：, m 代表字符集的大小。這次不論原字符串多小, 都會利用這么大的空間。

總結(jié)

綜上, 我們一步一步的尋求可優(yōu)化的地方, 對算法進(jìn)行了優(yōu)化。又加深了 Hash 的應(yīng)用, 以及利用數(shù)組巧妙的實(shí)現(xiàn)了 Hash 的作用。