专栏首页OBKoro1的前端分享前端中等算法-无重复字符的最长子串
原创

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

无重复字符的最长子串

难度:中等

描述:

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

样例:

  • 输入: "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) {
}

代码:

  1. 用对象储存字符的位置, 出现重复字符时更新不重复字符的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;
};
  1. 从左到右,一个字符一个字符搜索,看是否重复。
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;
};

<!-- 特殊字符串:用于修改/删除markdown的结尾提示语-OBKoro1 -->

点个Star支持我一下~

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JS 调用栈机制与 ES6 尾调用优化介绍

    调用栈的英文名叫做Call Stack,大家或多或少是有听过的,但是对于js调用栈的工作方式以及如何在工作中利用这一特性,大部分人可能没有进行过更深入的研究,这...

    OBKoro1
  • 论普通函数和箭头函数的区别以及箭头函数的注意事项、不适用场景

    箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程...

    OBKoro1
  • 教你如何填满过去一年的Github的绿色格子-Auto Commit

    如果提交到其他分支,提交记录不会显示在绿色的格子里面,合并分支之后 才会显示在绿色格子里面。

    OBKoro1
  • LuaJit转义的问题

    之前在项目中,处理类似!30转为表现的字符串时,有人写了这样的一段代码“\![1-2][0-9]”,当换成luajit时启动报错了,出错原因在于转义字符使用不对...

    meteoric
  • 艺术鬼才!Unicode 字符还能这么玩?

    上周的时候,朋友圈的直升飞机不知道为什么就火了,很多朋友开着各种花式飞机带着起飞。

    andyxh
  • LeetCode-8 字符串转换整数

    今天我们学习第8题字符串转换整数,这是一个字符串的中等题,像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我...

    用户3470542
  • Python基础(六)——面向对象编程

      注意一点:类中自定义的方法一定要含有 self 参数,但是在调用的时候,无需为此传递参数。

    py3study
  • 观点 | 人工智能的第三定律:计算的未来是模拟

    AI 科技评论按:在人工智能研究如火如荼的今天,似乎也是时候回过头来思考一下模拟计算在未来所具有的意义。当人类已经习惯于通过数字化编程控制机器,也许以神经网络为...

    AI科技评论
  • HTA2.0芯片数据分析比较麻烦,我也尝试给你一些思路

    不过最近学徒问到了[HTA-2_0] Affymetrix Human Transcriptome Array 2.0芯片的事情,其实挺麻烦的,首先需要搞清楚下...

    生信技能树
  • C# 使用相同权限调用 cmd 传入命令

    如果想要用相同的权限运行一个程序,可以使用 ProcessStartInfo 的方法

    林德熙

扫码关注云+社区

领取腾讯云代金券