前端中等算法-無重複字元的最長子串

無重複字元的最長子串

難度：中等

描述：

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

樣例：

• 輸入: "abcabcbb"

輸出: 3

解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。

• 輸入: "bbbbb"

輸出: 1

解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。

• 輸入: "pwwkew"

解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。

• 輸入: "dvdf"

解釋: 因為無重複字元的最長子串是 "vdf"，是以其長度為 3。

• 輸入: "asjrgapa"

輸出: 6

解釋: 因為無重複字元的最長子串是 "sjrgap"，是以其長度為 6。

• 輸入: "aabaab!bb"

解釋: 因為無重複字元的最長子串是 "ab!"，是以其長度為 3。

• 輸入: "abcb"

• 輸入: "asljlj"

輸出: 4

解釋: 因為無重複字元的最長子串是 "aslj"，是以其長度為 4。

• 輸入: "qwnfenpglqdq"

輸出: 8

解釋: 因為無重複字元的最長子串是 "fenpglqd"，是以其長度為 8。

思路分析：

關鍵在于在出現重複字元時，如何更新不重複字元的index

代碼模闆：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
}
           

想

一

再

看

答

案

代碼：

1. 用對象儲存字元的位置, 出現重複字元時更新不重複字元的index。

var lengthOfLongestSubstring = function (s) {
    let obj = {}; // 用于儲存字元出現的位置
    let res = 0; // 最大值
    let j = 0; // 不重複字元的index
    for (let i = 0; i < s.length; i++) {
        // 目前值是否在對象中存儲過
        const value = obj[s[i]]
        if (value !== undefined) {
            // 更新上一次重複值的index
            // value + 1 跳過之前重複的字元
            // j: 之前不重複的index 重複字元 需要全部跳過
            j = Math.max(value + 1, j)

        }
        // 每個字元都計算一下最長不重複值 儲存最大值
        // 不重複最長長度 = 目前index - 上一次重複值的index + index從0開始 長度從1開始
        res = Math.max(res, i - j + 1);
        // 存/更新 字元串index
        obj[s[i]] = i
    }
    return res;
};
           

1. 從左到右，一個字元一個字元搜尋，看是否重複。

var lengthOfLongestSubstring = function (s) {
    var i = 0, // 不重複字元的index
        res = 0; // 更新無重複字元的長度
    for (j = 0; j < s.length; j++) {
        // 查找：不重複字元-目前index之間 有沒有出現目前字元
        let index = s.slice(i, j).indexOf(s[j])
        if (index === -1) {
            // 更新無重複字元的長度：目前index-不重複字元的index + 長度從1開始算
            res = Math.max(res, j - i + 1);
        } else {
            // 更新i = 不重複字元的index
            // 不重複字元的index = 原不重複的字元index + i-j中出現重複字元的index + 跳過該重複字元
            i = i + index + 1;
        }
    }
    return res;
};
           

點個Star支援我一下~

GitHub：https://github.com/OBKoro1，

wx:OBkoro1，

郵箱：[email protected]