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

in #cn5 years ago

题目描述

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
};

运行结果

image.png

Sort:  

As a follower of @followforupvotes this post has been randomly selected and upvoted! Enjoy your upvote and have a great day!

This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.

You got a 10.00% upvote from @upvoteturtle. Thank you very much for using this upvote service. 😍
We would be very happy about a delegation to grow and increase the maximum upvote!😉
10SP 20SP 50SP 100SP 200SP
This voting Bot pays 100% out to all Delegators and gives an upvote Revenue of 120%