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

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

给定一个字符串 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 。我自己反思了一下，主要问题出在滑动上，这是明显的滑动窗口题目，但是我没有推出滑动的方式，反而通过模拟的方式来进行实现，因此造成耗时很久。

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