[LeetCode] 3. Longest Substring Without Repeating Characters 最長(zhǎng)無重復(fù)字符的子串

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

這道求最長(zhǎng)無重復(fù)子串的題和之前那道 Isomorphic Strings 很類似，屬于 LeetCode 早期經(jīng)典題目，博主認(rèn)為是可以跟 Two Sum 媲美的一道題。給了我們一個(gè)字符串，讓求最長(zhǎng)的無重復(fù)字符的子串，注意這里是子串，不是子序列，所以必須是連續(xù)的。先不考慮代碼怎么實(shí)現(xiàn)，如果給一個(gè)例子中的例子 "abcabcbb"，讓你手動(dòng)找無重復(fù)字符的子串，該怎么找。博主會(huì)一個(gè)字符一個(gè)字符的遍歷，比如 a，b，c，然后又出現(xiàn)了一個(gè)a，那么此時(shí)就應(yīng)該去掉第一次出現(xiàn)的a，然后繼續(xù)往后，又出現(xiàn)了一個(gè)b，則應(yīng)該去掉一次出現(xiàn)的b，以此類推，最終發(fā)現(xiàn)最長(zhǎng)的長(zhǎng)度為3。所以說，需要記錄之前出現(xiàn)過的字符，記錄的方式有很多，最常見的是統(tǒng)計(jì)字符出現(xiàn)的個(gè)數(shù)，但是這道題字符出現(xiàn)的位置很重要，所以可以使用 HashMap 來建立字符和其出現(xiàn)位置之間的映射。進(jìn)一步考慮，由于字符會(huì)重復(fù)出現(xiàn)，到底是保存所有出現(xiàn)的位置呢，還是只記錄一個(gè)位置？我們之前手動(dòng)推導(dǎo)的方法實(shí)際上是維護(hù)了一個(gè)滑動(dòng)窗口，窗口內(nèi)的都是沒有重復(fù)的字符，需要盡可能的擴(kuò)大窗口的大小。由于窗口在不停向右滑動(dòng)，所以只關(guān)心每個(gè)字符最后出現(xiàn)的位置，并建立映射。窗口的右邊界就是當(dāng)前遍歷到的字符的位置，為了求出窗口的大小，需要一個(gè)變量 left 來指向滑動(dòng)窗口的左邊界，這樣，如果當(dāng)前遍歷到的字符從未出現(xiàn)過，那么直接擴(kuò)大右邊界，如果之前出現(xiàn)過，那么就分兩種情況，在或不在滑動(dòng)窗口內(nèi)，如果不在滑動(dòng)窗口內(nèi)，那么就沒事，當(dāng)前字符可以加進(jìn)來，如果在的話，就需要先在滑動(dòng)窗口內(nèi)去掉這個(gè)已經(jīng)出現(xiàn)過的字符了，去掉的方法并不需要將左邊界 left 一位一位向右遍歷查找，由于 HashMap 已經(jīng)保存了該重復(fù)字符最后出現(xiàn)的位置，所以直接移動(dòng) left 指針就可以了。維護(hù)一個(gè)結(jié)果 res，每次用出現(xiàn)過的窗口大小來更新結(jié)果 res，就可以得到最終結(jié)果啦。

這里可以建立一個(gè) HashMap，建立每個(gè)字符和其最后出現(xiàn)位置之間的映射，然后需要定義兩個(gè)變量 res 和 left，其中 res 用來記錄最長(zhǎng)無重復(fù)子串的長(zhǎng)度，left 指向該無重復(fù)子串左邊的起始位置的前一個(gè)，由于是前一個(gè)，所以初始化就是 -1，然后遍歷整個(gè)字符串，對(duì)于每一個(gè)遍歷到的字符，如果該字符已經(jīng)在 HashMap 中存在了，并且如果其映射值大于 left 的話，那么更新 left 為當(dāng)前映射值。然后映射值更新為當(dāng)前坐標(biāo)i，這樣保證了 left 始終為當(dāng)前邊界的前一個(gè)位置，然后計(jì)算窗口長(zhǎng)度的時(shí)候，直接用 i-left 即可，用來更新結(jié)果 res。

這里解釋下程序中那個(gè) if 條件語句中的兩個(gè)條件 m.count(s[i]) && m[s[i]] > left，因?yàn)橐坏┊?dāng)前字符 s[i] 在 HashMap 已經(jīng)存在映射，說明當(dāng)前的字符已經(jīng)出現(xiàn)過了，而若 m[s[i]] > left 成立，說明之前出現(xiàn)過的字符在窗口內(nèi)，那么如果要加上當(dāng)前這個(gè)重復(fù)的字符，就要移除之前的那個(gè)，所以讓 left 賦值為 m[s[i]]，由于 left 是窗口左邊界的前一個(gè)位置（這也是 left 初始化為 -1 的原因，因?yàn)榇翱谧筮吔缡菑?開始遍歷的），所以相當(dāng)于已經(jīng)移除出滑動(dòng)窗口了。舉一個(gè)最簡(jiǎn)單的例子 "aa"，當(dāng) i=0 時(shí)，建立了 a->0 的映射，并且此時(shí)結(jié)果 res 更新為1，那么當(dāng) i=1 的時(shí)候，發(fā)現(xiàn)a在 HashMap 中，并且映射值0大于 left 的 -1，所以此時(shí) left 更新為0，映射對(duì)更新為 a->1，那么此時(shí) i-left 還為1，不用更新結(jié)果 res，那么最終結(jié)果 res 還為1，正確，代碼如下：

C++ 解法一： 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, left = -1, n = s.size();
        unordered_map<int, int> m;
        for (int i = 0; i < n; ++i) {
            if (m.count(s[i]) && m[s[i]] > left) {
                left = m[s[i]];  
            }
            m[s[i]] = i;
            res = max(res, i - left);            
        }
        return res;
    }
};

下面這種寫法是上面解法的精簡(jiǎn)模式，這里我們可以建立一個(gè) 256 位大小的整型數(shù)組來代替 HashMap，這樣做的原因是 ASCII 表共能表示 256 個(gè)字符，但是由于鍵盤只能表示 128 個(gè)字符，所以用 128 也行，然后全部初始化為 -1，這樣的好處是不用像之前的 HashMap 一樣要查找當(dāng)前字符是否存在映射對(duì)了，對(duì)于每一個(gè)遍歷到的字符，直接用其在數(shù)組中的值來更新 left，因?yàn)槟J(rèn)是 -1，而 left 初始化也是 -1，所以并不會(huì)產(chǎn)生錯(cuò)誤，這樣就省了 if 判斷的步驟，其余思路都一樣：

C++ 解法二：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> m(128, -1);
        int res = 0, left = -1;
        for (int i = 0; i < s.size(); ++i) {
            left = max(left, m[s[i]]);
            m[s[i]] = i;
            res = max(res, i - left);
        }
        return res;
    }
};

Java 解法二：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] m = new int[256];
        Arrays.fill(m, -1);
        int res = 0, left = -1;
        for (int i = 0; i < s.length(); ++i) {
            left = Math.max(left, m[s.charAt(i)]);
            m[s.charAt(i)] = i;
            res = Math.max(res, i - left);
        }
        return res;
    }
}

下面這種解法使用了 HashSet，核心算法和上面的很類似，把出現(xiàn)過的字符都放入 HashSet 中，遇到 HashSet 中沒有的字符就加入 HashSet 中并更新結(jié)果 res，如果遇到重復(fù)的，則從左邊開始刪字符，直到刪到重復(fù)的字符停止：

C++ 解法三：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, left = 0, i = 0, n = s.size();
        unordered_set<char> t;
        while (i < n) {
            if (!t.count(s[i])) {
                t.insert(s[i++]);
                res = max(res, (int)t.size());
            }  else {
                t.erase(s[left++]);
            }
        }
        return res;
    }
};

Java 解法三：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, left = 0, right = 0;
        HashSet<Character> t = new HashSet<Character>();
        while (right < s.length()) {
            if (!t.contains(s.charAt(right))) {
                t.add(s.charAt(right++));
                res = Math.max(res, t.size());
            } else {
                t.remove(s.charAt(left++));
            }
        }
        return res;
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)leetcode(3.最長(zhǎng)無重復(fù)字符的子串)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最長(zhǎng)無重復(fù)字符的子串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論