LeetCode 3 | Longest Substring Without Repeating Characters 无重复字符的最长子串

题目描述

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.

题目意思就是， 给一个字符串， 找到字符串中， 没有重复字符的最长的子串的长度

分析

最容易想到的， 依然是暴力遍历， 用两层for循环遍历字符串s中的每一个子串，再对每个子串循环遍历计算不重复的长度， 这样有三层遍历的关系，时间复杂度O(n ^ 3)

显然这样太慢了， 反复检查每一个字符串其实是有冗余操作的，不必要检查每一段子串，因为如果下标从 i 到 j 都是不重复的元素， 我们只要检查 第 j+1个元素是否存在于下标 i — j之间就可以了。

可以用两个指针 left, i 指向字符串第一位， 然后遍历循环 i， 如果字符串中下标为 i 的值不在hash表中， 则说明当前字符没出现过，当前长度 cL 加1， 反之，如果在hash表中有下标为 i 的值， 说明之前该字符已出现过， 则我们要滑动检查字符串的左边界 left， 将它滑动到当前位置，更新检查的范围。

我的Javascript解法

/**
 * @param {string}
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let l = s.length
    // 先过滤掉边界情况
    if (l <= 1) { return l }

    let hash = {}

    // 滑动窗口(遍历检查字符串)的左边界
    let left = 0

    // 当前长度
    let cL = 0

    // 最终确定的最长长度
    let fL = 0
    for (let i =0; i < l; i++) {
        let t = s[i]

        // 如果当前hash表中，出现了当前字符， 说明之前出现过
        if (hash[t] >= left) {

            // 更新左边界为hash表中之前存的字符位置
            left = hash[t]

            // 根据当前下标，左边界下标， 计算长度
            cL = i - left
        } else {

           // 没有出现在hash表中， 说明之前没出现过该字符， 长度加一
            cL++
        }
          // 把当前字符的位置， 储存在hash表中记录下来
        hash[t] = i

        // 如果当前的长度比最大长度还大， 则更新最大长度为当前长度
        if (cL > fL) {
            fL = cL
        }
    }
    return fL
};

运行结果