跳至主要內容

Mr.He大约 1 分钟

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 哈希集合,记录每个字符是否出现过
    const set = new Set();
    const n = s.length;
    // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
    let right = -1;
    let maxLen = 0;
    
    for (let left = 0; left < n; left++) {
        // 左指针向右移动一格,移除一个字符
        if (left !== 0) {
            set.delete(s.charAt(left - 1));
        }
        
        // 不断地向右移动右指针,直到遇到重复字符或者到达字符串末尾
        while (right + 1 < n && !set.has(s.charAt(right + 1))) {
            set.add(s.charAt(right + 1));
            right++;
        }
        
        // 第 left 到 right 个字符是一个极长的无重复字符子串
        // 长度为 right - left + 1
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};

更简洁的写法(优化版)

下面这种写法逻辑更直观:遇到重复字符时,直接收缩左边界。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let maxLen = 0;
    let left = 0;
    const charSet = new Set();

    for (let right = 0; right < s.length; right++) {
        // 当前字符
        const currentChar = s[right];

        // 如果 Set 中存在该字符,说明重复了
        // 移动左指针,并删除左指针经过的字符,直到 Set 中不包含当前字符
        while (charSet.has(currentChar)) {
            charSet.delete(s[left]);
            left++;
        }

        // 将当前字符加入 Set
        charSet.add(currentChar);
        
        // 更新最大长度 (当前窗口大小为 right - left + 1)
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
};