算法 1.8 無重復(fù)字符的最長(zhǎng)子串【leetcode 3】

題目描述

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度

數(shù)據(jù)結(jié)構(gòu)

  • 數(shù)組、指針、哈希表

算法思維

  • 雙指針、哈希（散列）

解題要點(diǎn)

  • “范圍問題” 或 “同步變化” ==> 雙指針
  • “快速查找” 或 “重復(fù)匹配” ==> 哈希表

關(guān)鍵知識(shí)點(diǎn)：哈希表 與 哈希算法
Hash table：哈希表，也叫散列表
? 把關(guān)鍵碼值映射到表中的一個(gè)位置，以加快查找速度
Hash 算法
? 散列值：把任意長(zhǎng)度的輸入通過算法變成固定長(zhǎng)度的輸出
? 是一種壓縮映射，直接取余操作
? 哈希沖突的解決：開放尋址；再散列；鏈地址法；
位運(yùn)算
? & | ~ ^ << >> >>>
? 取模操作： a % (Math.pow(2,n)) ? 33 % 16 = 1
? 等價(jià)于：a & (Math.pow(2,n)-1) ? 33 & 15 = 1


解題步驟

一. Comprehend 理解題意
1. 題目主干要求
  • 返回最長(zhǎng)子串的長(zhǎng)度
  • 子串中無重復(fù)字符
  • 子串，而非子序列："wke"是子串，"pwke"是子序列
2. 其它細(xì)節(jié)
  • 測(cè)試數(shù)據(jù)僅包含 ASCII 碼表中的字符
  • 字符串可能為空，或全部由空字符組成
解法一：暴力解法
  1. 先找到所有不重復(fù)子串，再統(tǒng)計(jì)最長(zhǎng)子串的長(zhǎng)度
  2. 查找子串時(shí)，只保留不含重復(fù)字符的串
  3. 需要將這些子串臨時(shí)存儲(chǔ)在一個(gè)容器中
  4. 使用語言特性（Java）
解法二：優(yōu)化解法
  1. 在原字符串上定位并計(jì)算子串長(zhǎng)度，取最大值
  2. 查找不含重復(fù)字符的子串，通過索引計(jì)算其長(zhǎng)度
  3. 每次計(jì)算與上次子串長(zhǎng)度對(duì)比，只保留最大的數(shù)值


二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法
解法一：統(tǒng)計(jì)最長(zhǎng)子串的長(zhǎng)度
  • 數(shù)據(jù)結(jié)構(gòu)：數(shù)組/棧/鏈表/隊(duì)列+字符串
  • 算法思維：遍歷+雙指針（外層循環(huán)start，內(nèi)層循環(huán)end）
解法二：計(jì)算并保留最大子串長(zhǎng)度
  • 數(shù)據(jù)結(jié)構(gòu)：字符串（臨時(shí)子串）
  • 算法思維：遍歷+雙指針


三. Code 編碼實(shí)現(xiàn)基本解法
解法一：暴力解法思路分析
  1. 生成所有不包含重復(fù)字符的子串
    將所有單字符子串添加到集合（ArrayList）中
    遍歷字符串，外層循環(huán)為 start，內(nèi)層為 end
    截取不含重復(fù)字符的子串，添加到集合中
  2. 統(tǒng)計(jì)最長(zhǎng)子串的長(zhǎng)度
    遍歷集合，統(tǒng)計(jì)最大子串長(zhǎng)度并返回
邊界問題
  • 遍歷字符串的字符，注意索引越界
  • 生成子串時(shí)，注意子串的起止索引
細(xì)節(jié)問題
  • 子串添加到 ArrayList，它會(huì)動(dòng)態(tài)擴(kuò)容
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length;
        if(s == null || (length = s.length()) == 0) return 0;
        // 1.生成所有不包含重復(fù)字符的子串
        List < String > list = new ArrayList < > ();
        list.addAll(Arrays.asList(s.split(""))); // 單字符，直接添加到集合中
        for(int start = 0; start < length; start++) { // 遍歷子串的起始字符
            for(int end = start + 1; end < length; end++) { // 遍歷子串的終止字符
                String subStr = s.substring(start, end);
                // 當(dāng)前字符在前面的子串中已出現(xiàn)，則跳過該字符
                if(subStr.indexOf(s.charAt(end)) != -1) {
                    break;
                }
                list.add(s.substring(start, end + 1)); // 否則，添加到集合中
            }
        }
        // 2.統(tǒng)計(jì)最長(zhǎng)子串的長(zhǎng)度
        int maxLength = 1;
        for(String sub: list) {
            int subLen;
            if((subLen = sub.length()) > maxLength) maxLength = subLen;
        }
        return maxLength;
    }
}

時(shí)間復(fù)雜度：O(n3)
? ? 將字符串切割成單字符數(shù)組：O(n)
? ? 遍歷并截取子串：O(n3)
? ? 統(tǒng)計(jì)最長(zhǎng)子串長(zhǎng)度：O(n2)
? ? 實(shí)際時(shí)間消耗巨大
空間復(fù)雜度：O(n2)
? ? 數(shù)組列表：O(n2)，理論上最多有 n(n + 1) / 2 個(gè)子串
? ? 子串都是常量：O(n2)
? ? 子串都是字符串常量，實(shí)際空間消耗巨大
執(zhí)行耗時(shí)：270 ms，擊敗了 6.86% 的Java用戶
內(nèi)存消耗：39.8 MB，擊敗了 5.04% 的Java用戶

解法二：優(yōu)化解法解法思路分析
  1. 定義變量 maxLength 表示最大長(zhǎng)度
  2. 使用雙指針截取不含重復(fù)字符的子串
  3. 計(jì)算子串長(zhǎng)度，保留較大值到 maxLength
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len;
        if(s == null || (len = s.length()) == 0) {
            return 0;
        }
        int maxLength = 1; // 最長(zhǎng)子串的長(zhǎng)度。默認(rèn)值1：原字符串有數(shù)據(jù)，至少是1
        // 1.遍歷字符串，生成所有的不含重復(fù)字符的子串
        for(int start = 0; start < len; start++) { // 遍歷子串的起始字符
            for(int end = start + 1; end < len; end++) { // 遍歷子串的終止字符
                String subStr = s.substring(start, end); // 截取當(dāng)前字符的前置子串
                // 當(dāng)前字符在前面的子串中已出現(xiàn)，則跳過該字符
                if(subStr.indexOf(s.charAt(end)) != -1) {
                    break;
                }
                // 2.統(tǒng)計(jì)最長(zhǎng)子串的長(zhǎng)度
                int subLen = end + 1 - start; // 子串長(zhǎng)度
                if(subLen > maxLength) maxLength = subLen;
            }
        }
        return maxLength;
    }
}

時(shí)間復(fù)雜度：O(n3)
? ? 將字符串切割成單字符數(shù)組：O(n)
? ? 遍歷并截取子串：O(n3)
? ? 統(tǒng)計(jì)最長(zhǎng)子串長(zhǎng)度：O(n2)
? ? 實(shí)際時(shí)間消耗巨大
空間復(fù)雜度：O(n2)
? ? 數(shù)組列表：O(n2)，理論上最多有 n(n + 1) / 2 個(gè)子串
? ? 子串都是常量：O(n2)
? ? 子串都是字符串常量，實(shí)際空間消耗巨大
執(zhí)行耗時(shí)：260 ms，擊敗了 7.06% 的Java用戶
內(nèi)存消耗：39.4 MB，擊敗了 6.54% 的Java用戶


四. Consider 思考更優(yōu)解
剔除無效代碼或優(yōu)化空間消耗
  • 能否不存儲(chǔ)子串？
  • 能否避免生成字符串常量？
尋找更好的算法思維
  • 能否只掃描一遍字符串？
  • 定位子串并檢查重復(fù)字符的過程比較耗時(shí)，能否優(yōu)化？
  • 參考其它算法


五. Code 編碼實(shí)現(xiàn)最優(yōu)解
最優(yōu)解：哈希表 + 雙指針 解法
  1. 定義哈希表，臨時(shí)存儲(chǔ)子串字符和查重
    定義哈希函數(shù)，對(duì)任意字符生成唯一整數(shù)值
  2. 遍歷字符串，通過雙指針循環(huán)定位子串
    重復(fù)檢查右指針元素是否存在與哈希表中；
    ? 是，刪除哈希表中左指針元素，移動(dòng)左指針
    ? 否，記錄到哈希表，計(jì)算長(zhǎng)度，移動(dòng)右指針
  3. 每次計(jì)算子串長(zhǎng)度，比較并保留最大值
邊界問題
  • 遍歷字符串的字符，注意索引越界
  • 計(jì)算子串長(zhǎng)度時(shí)，注意子串的起止索引
  • 根據(jù)測(cè)試用例，子串長(zhǎng)度不會(huì)超過哈希表容量：new char[128]
細(xì)節(jié)問題
  • 子串長(zhǎng)度是：end + 1 - start
  • 出現(xiàn)重復(fù)元素后，左指針逐個(gè)移動(dòng)，直到與當(dāng)前重復(fù)的字符索引+1
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, left = 0, right = 0, len = s.length();
        // 1.定義哈希表，支持ASCII碼表的全部字符
        char[] chs = new char[128];
        // 2.遍歷字符串的所有字符
        while(right < len) { // 右指針后移，不超過源字符串長(zhǎng)度
            char rightChar = s.charAt(right); // 右指針字符
            char c = chs[(chs.length - 1) & hash(rightChar)]; // hash算法計(jì)算索引
            if(rightChar != c) { // 未重復(fù)出現(xiàn)
                // 2.1.記錄到哈希表，移動(dòng)右指針，計(jì)算長(zhǎng)度
                char v = s.charAt(right++);
                // 將不重復(fù)字符記錄到哈希表中
                chs[(chs.length - 1) & hash(v)] = v;
                // 3.每次記錄子串長(zhǎng)度，并計(jì)算最大值
                int size = right - left; // 每個(gè)不重復(fù)子串的長(zhǎng)度
                res = res > size ? res : size; // 取較大值
            }
            else { // 重復(fù)出現(xiàn)
                // 2.2.刪除左指針元素，移動(dòng)左指針。重復(fù)檢查右指針元素是否還存在
                char leftChar = s.charAt(left++);
                chs[(chs.length - 1) & hash(leftChar)] = '\u0000';
            }
        }
        return res;
    }
}

時(shí)間復(fù)雜度：O(n) -- 遍歷字符串 O(n)，定位重復(fù)字符 O(1)
空間復(fù)雜度：O(1) -- 哈希表占用固定空間 O(1)，雙指針 O(1)
執(zhí)行耗時(shí)：4 ms，擊敗了 90.12% 的Java用戶
內(nèi)存消耗：38.8 MB，擊敗了 84.17% 的Java用戶

思路再優(yōu)化
  1. 哈希表作用變形
    字符ASCII碼值 --> 字符
    字符ASCII碼值 --> 字符最后出現(xiàn)索引
  2. 遇到重復(fù)元素后，左指針移動(dòng)優(yōu)化
    逐個(gè)移動(dòng)到前一個(gè)相同字符出現(xiàn)后的位置 --> 一次性定位到前一個(gè)相同字符出現(xiàn)后的位置
再優(yōu)化解法
  1. 初始化哈希表，存入非 ASCII 碼值作為默認(rèn)值
  2. 遍歷字符串，使用雙指針定位子串索引
    字符已出現(xiàn)：取出哈希表中記錄，左指針到記錄+1
    無論是否出現(xiàn)，將右指針記錄到哈希表
  3. 每次移動(dòng)都記錄子串長(zhǎng)度，保留最大值
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, // 最長(zhǎng)子串的計(jì)算結(jié)果
            left = 0, // 子串起始索引
            right = 0, // 子串結(jié)束索引
            len = s.length(); // 字符串長(zhǎng)度
        // 1.哈希表中填充ASCII碼表不包含的數(shù)值作為默認(rèn)值：-1
        int[] arr = new int[128];
        for(int i = 0; i < arr.length; i++) arr[i] = -1;
        // 2.遍歷字符串的所有字符
        while(right < len) {
            int c = s.charAt(right);
            if(arr[c] != -1) { // 檢測(cè)該字符是否已出現(xiàn)：已出現(xiàn)
                // 出現(xiàn)，則移動(dòng)左指針，直接定位到上次出現(xiàn)的下一個(gè)索引
                int start0 = arr[c] + 1;
                // 2.1.使用雙指針定位子串索引：左指針直接定位
                left = left >= start0 ? left : start0; // 只往右不往左
            }
            arr[c] = right; // 無論是否重復(fù)，記錄該字符最后一次出現(xiàn)的索引
            // 3.計(jì)算子串長(zhǎng)度，記錄最大值：右索引+1 - 左索引
            int size = right + 1 - left;
            res = res > size ? res : size;
            // 2.2.使用雙指針定位子串索引：右指針始終自增
            right++;
        }
        return res;
    }
}

時(shí)間復(fù)雜度：O(n) -- 遍歷字符串 O(n)，定位重復(fù)字符 O(1)
空間復(fù)雜度：O(1) -- 哈希表占用固定空間 O(1) ，雙指針 O(1)
執(zhí)行耗時(shí)：2 ms，擊敗了 100% 的Java用戶
內(nèi)存消耗：38.7 MB，擊敗了 96.69% 的Java用戶

自實(shí)現(xiàn)代碼：
class Solution {
    public int lengthOfLongestSubstring(String s) {

        int len = 0; //字符串長(zhǎng)度
        int subLen = 0; //子串長(zhǎng)度

        //0.非空判斷
        if (s == null || (len = s.length()) == 0) return 0;

        //1.定義哈希表，臨時(shí)存儲(chǔ)子串字符和查重
        char[] hashtable = new char[128];

        char[] arr = s.toCharArray();
        int left = 0;
        int right = 0;
        //2.遍歷字符串，通過雙指針循環(huán)定位子串
        while (left < len) {
            //判斷右指針在哈希表中是否存在
            if (hashtable[hash(arr[right])] == '\u0000') {
                //不存在，記錄到哈希表，計(jì)算長(zhǎng)度，移動(dòng)右指針
                hashtable[hash(arr[right])] = arr[right];
                //3.每次計(jì)算子串長(zhǎng)度，比較并保留最大值
                if (subLen < (right - left + 1)) {
                    subLen = right - left + 1;
                }
                if (right < len - 1) {
                    right++;
                }
            } else {
                //重復(fù)檢查右指針元素是否還存在
                while (hashtable[hash(arr[right])] != '\u0000') {
                    //若存在，刪除哈希表中左指針元素，移動(dòng)左指針
                    hashtable[hash(arr[left])] = '\u0000';
                    left++;
                }
            }
        }

        return subLen;
    }

    //定義哈希函數(shù)，對(duì)任意字符生成唯一整數(shù)值
    private int hash(char c) {
        return c;
    }
}

執(zhí)行耗時(shí)：3 ms，擊敗了 95.16% 的Java用戶
內(nèi)存消耗：38.3 MB，擊敗了 93.04% 的Java用戶


六. Change 變形與延伸
題目變形
  • （練習(xí)）使用Set集合改進(jìn)暴力解法
  • （練習(xí)）使用Map集合實(shí)現(xiàn)哈希表解法
延伸擴(kuò)展
  • 合理的使用雙指針能將時(shí)間復(fù)雜度從 O(n2) 降低到 O(n) 級(jí)別
  • 哈希表應(yīng)用廣泛，是非常重要的數(shù)據(jù)結(jié)構(gòu)（比如 HashMap）
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容