写点什么

【刷题第三天】无重复字符的最长字串

作者:白日梦
  • 2022 年 5 月 09 日
  • 本文字数:921 字

    阅读完需:约 3 分钟

一、题目描述:

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

示例

示例 1:

输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

二、思路分析:

这肯定是个滑动窗口的题目,但是我没有发现这个窗口如何滑动,因此我就想了这样一种办法。

题目要求是无重复字符串,因此我决定设置一对象 alpha 记录每个字母第一次出现的位置,举个栗子:

str = 'abcac'

遍历前三个字符后,alpha 改变为 {a: 0, b:1, c:2}

接着往后遍历,发现 alpha['a'] = 0 ,说明前面已经出现过 a 字符,因此比较此时的无重复长度与最大长度的大小,然后截断 a 字符以前的字符(重新赋值为 undefined),即 alpha['a'] = undefined,然后重新赋值当前字母新位置,即 alpha['a'] = 3

继续往后遍历,发现 alpha['c'] = 2 ,说明前面仍然出现出重复 c ,依次运行上述流程,即 alpha['b'] = undefined,alpha['c'] = undefined。然后重新赋予当前字母位置。

思路好像看起来就挺复杂的,但是的确可以成功 OA

三、AC 代码:

var lengthOfLongestSubstring = function (s) {  if (s.length === 1) {    return 1;  }  const alpha = {};  let maxLen = 0;  let count = 0;  for (let i = 0; i < s.length; i++) {    if (alpha[s[i]] || alpha[s[i]] === 0) {      maxLen = Math.max(maxLen, count);      count = i - alpha[s[i]];      const nowLeft = alpha[s[i]];      Object.keys(alpha).forEach((al) => {        if (alpha[al] <= nowLeft) {          alpha[al] = undefined;        }      });      alpha[s[i]] = i;    } else {      count++;      alpha[s[i]] = i;    }  }  return Math.max(maxLen, count);};复制代码
复制代码

四、总结:



通过最后的 AC 时间,我可以看到,当前使用的算法效率是非常低的,差点 Time Out 。我自己反思了一下,主要问题出在滑动上,这是明显的滑动窗口题目,但是我没有推出滑动的方式,反而通过模拟的方式来进行实现,因此造成耗时很久。

好慢的做法,明天的目标是不看题解思考出滑动窗口的运行方式,然后重做这个题目。


发布于: 刚刚阅读数: 2
用户头像

白日梦

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

评论

发布
暂无评论
【刷题第三天】无重复字符的最长字串_5月月更_白日梦_InfoQ写作社区