劍指Offer——最長不含重複字元的子字元串（JS實作）

題目描述

解題思路

• 本題采用哈希表 + 滑動視窗的思路
• 哈希表用來存儲每個字元出現的次數，當單個字元出現2次的時候，用以輔助我們移動滑動視窗
• 首先定義一個左右指針，左指針和右指針初始時指向0，右指針不斷右移作為判斷循環的條件，當右指針移動到字元串長度的位置時，結束循環。
• 具體過程看注釋，注釋很詳細

解題代碼（模拟隊列）

var lengthOfLongestSubstring = function (s) {
    // !本題采用滑動視窗 + 哈希表的方法解決
    // 定義滑動視窗，這個滑動視窗是一個哈希表，哈希表的鍵：單個字元 值：該字元出現的次數
    const window = new Map();
    // 定義左指針
    let left = 0;
    // 定義右指針
    let right = 0;
    // 定義不重複子串的最大長度
    let res = 0;
    // 右指針小于字元串的長度的時候，是進入循環的條件
    while (right < s.length) {

        // 因為我們移動的是右指針，是以要先判斷哈希表中是否含有右指針指向的元素
        if (window.has(s[right])) {
            window.set(s[right],window.get(s[right]) + 1);
        } else {
            window.set(s[right],1);
        }
        // 判斷右指針指向的元素是否出現重複
        while (window.get(s[right]) > 1) {
            // 左指針指向的元素出現的次數-1，然後左指針右移，直到出現重複的那個元素不再重複
            window.set(s[left],window.get(s[left]) - 1);
            left++;
        }
        right++;
        res = Math.max(res,right - left);
    }
    return res;
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用滑動視窗 + 哈希表
• 啟示二：學會使用雙指針
• 啟示三：學會通過更新的方式擷取到最大值