前端中等算法-无重复字符的最长子串

hyuan 发布于2019-08-26 10:40 / 1288人阅读

摘要：无重复字符的最长子串难度中等描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。输入输出解释因为无重复字符的最长子串是，所以其长度为。

无重复字符的最长子串 难度：中等 描述：

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

样例：

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

输入: "dvdf"

输出: 3

解释: 因为无重复字符的最长子串是 "vdf"，所以其长度为 3。

输入: "asjrgapa"

输出: 6

解释: 因为无重复字符的最长子串是 "sjrgap"，所以其长度为 6。

输入: "aabaab!bb"

输出: 3

解释: 因为无重复字符的最长子串是 "ab!"，所以其长度为 3。

输入: "abcb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "asljlj"

输出: 4

解释: 因为无重复字符的最长子串是 "aslj"，所以其长度为 4。

输入: "qwnfenpglqdq"

输出: 8

解释: 因为无重复字符的最长子串是 "fenpglqd"，所以其长度为 8。

思路分析：

关键在于在出现重复字符时，如何更新不重复字符的index

代码模板：

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

想一想再看答案 代码：

用对象储存字符的位置, 出现重复字符时更新不重复字符的index。

var lengthOfLongestSubstring = function (s) {
    let obj = {}; // 用于储存字符出现的位置
    let res = 0; // 最大值
    let j = 0; // 不重复字符的index
    for (let i = 0; i < s.length; i++) {
        // 当前值是否在对象中存储过
        const value = obj[s[i]]
        if (value !== undefined) {
            // 更新上一次重复值的index
            // value + 1 跳过之前重复的字符
            // j: 之前不重复的index 重复字符 需要全部跳过
            j = Math.max(value + 1, j)

        }
        // 每个字符都计算一下最长不重复值 保存最大值
        // 不重复最长长度 = 当前index - 上一次重复值的index + index从0开始 长度从1开始
        res = Math.max(res, i - j + 1);
        // 存/更新 字符串index
        obj[s[i]] = i
    }
    return res;
};

从左到右，一个字符一个字符搜索，看是否重复。

var lengthOfLongestSubstring = function (s) {
    var i = 0, // 不重复字符的index
        res = 0; // 更新无重复字符的长度
    for (j = 0; j < s.length; j++) {
        // 查找：不重复字符-当前index之间 有没有出现当前字符
        let index = s.slice(i, j).indexOf(s[j])
        if (index === -1) {
            // 更新无重复字符的长度：当前index-不重复字符的index + 长度从1开始算
            res = Math.max(res, j - i + 1);
        } else {
            // 更新i = 不重复字符的index
            // 不重复字符的index = 原不重复的字符index + i-j中出现重复字符的index + 跳过该重复字符
            i = i + index + 1;
        }
    }
    return res;
};

点个Star支持我一下~

云服务器 GPU云服务器字符串找子串算法最长公共子串 java最长相同子串字符串去重复高效算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106573.html

LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
【leetcode】3. 无重复字符的最长子串

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。完成循环后取队列中出现的最大长度即可。给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2：输入: bbbbb 输出: 1 解释:...

qc1iu 2019-08-23 18:32 评论0 收藏0
Leetcode 3 Longest Substring Without Repeat... 最长无

摘要：难度题意是求最长无重复子串给出一个字符串从所有子串中找出最长且没有重复字母的子串的长度我的解法是以为例使用一个记录当前子串遇到的所有字符用一个游标从头开始读取字符加入到中如果碰到了重复字符遇到了重复则从当前子串的头部的字符开始将该字符从中移 Longest Substring Without Repeating CharactersGiven a string, find the le...

RyanHoo 2019-08-14 17:01 评论0 收藏0
LeetCode3.无重复字符的最长子串JavaScript

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。 LeetCode3.无重复字符的最长子串JavaScript 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2: 输入: bbbbb输出...

vboy1010 2019-08-23 14:46 评论0 收藏0