题目描述

Longest Substring Without Repeating Characters

给定一个字符串 s，找出长度最长且不包含重复字符的子串的长度

示例1：

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

示例2：

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

示例3：

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

示例4：

Input: s = ""
Output: 0

另满足：

• 0 <= s.length <= 5 * 104
• s的组成为英文字符，数字，符号或者空格

javascript:

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

From leetcode No.3 Medium (opens new window)

解法

点击查看

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0){
        return 0
    }
    let map = {};
    let start = 0;
    let end = 0
    let max = 0
    while(end < s.length){
        const index = map[s[end]];
        if(index === undefined){
            map[s[end]] = end;
            max = Math.max(max, end - start + 1)
            end++;
        }else{
            start = index + 1;
            end = start;
            map = {};
        }
    }
    return max;
}

点击查看

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0){
        return 0
    }
    let map = {};
    let start = 0;
    let end = 0
    let max = 0
    while(end < s.length){
        const index = map[s[end]];
        if(index !== undefined && index >= start){
            start = index + 1;
            map[s[end]] = end; // 重复利用map
            end++; //跳过重复项
        }else{
            map[s[end]] = end;
            max = Math.max(max, end - start + 1)
            end++;
        }
    }
    return max;
};

总结

• 找子串自然想到双指针，分别对应起点和终点索引
• 因为仅仅需要返回长度，故使用一个变量存储，比对更新即可
• 去重自然想到哈希表
  • 但这里是局部去重，即在起点和终点的这个范围内不重复就好
• 确认起点和终点的位置
  • 当终点指针指向的值重复时，把起点指针移到重复位置后一位
    • 也可以是原起始指针后移一位，但明显有重复，不是最优解

学习速度最快的解法, 思路差不多，使用了 Set数据结构来代替哈希表，作用类似，且会将起始索引之前的记录值删掉， 始终保持为一个不重复的子序列

点击查看

var lengthOfLongestSubstring = function(s) {
    let start = 0, end = 0, max = 0;
    const length = s.length;
    const set = new Set();
    
    while (end < length) {
        if (!(set.has(s[end]))) {
            set.add(s[end]);
            max = Math.max(max, end - start + 1);
        } else {
            while (set.has(s[end])) {
                set.delete(s[start]);
                start++;
            }
            set.add(s[end]);
        }
        end++;
    }
    
    return max;
};