21-05-31-无重复字符的最长子串

题目地址

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目描述

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

示例 1:

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

示例 2:

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路1

两层循环暴力破解。

代码

var lengthOfLongestSubstring = function (s) {
  const length = s.length;
  if (length <= 1) return length;
  let prevMaxLength = 0;
  for (let i = 0; i < length; i++) {
    if (s.length - i <= prevMaxLength) break; // 如果到尾部都小于当前的最大，就直接跳出循环
    let map = new Map();
    map.set(s[i], true);
    for (let j = i + 1; j < length; j++) {
      if (!map.has(s[j])) {
        map.set(s[j], true);
      } else {
        break;
      }
    }
    if (map.size > prevMaxLength) {
      prevMaxLength = map.size;
    }
  }
  return prevMaxLength;
};

复杂度分析

• 时间复杂度：O(N^2)
• 空间复杂度：O(N)

思路2

双指针，滑动窗口，哈希集合。哈希集合用来记录访问的点。左指针步进一步，右指针可以直接步进到上次导致重复的地方。

举个例子：abcdefabc 第一个循环，我们找到以a开头的最长子串abcdef，下次我们要找b开头的不重复子串，经上次计算我们知悉了bcdef肯定已经是不重复了，所以此时我们的右指针可以直接从f后面即a的位置开始扫描，当然每次循环我们应该剔除掉上一次的头部字符，即开头的a字符。

代码

var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) return s.length;
  let res = 0;
  const set = new Set([]);
  for (let i = 0, j = 0; i < s.length; i++) {
    if (i > 0) {
      set.delete(s[i - 1]); // 移除前一位
    }
    while (j < s.length && !set.has(s[j])) {
      set.add(s[j]);
      j ++;
    }
    res = Math.max(res, j - i);
  }
  return res;
};

复杂度分析

• 时间复杂度：O(N)，每个字符被扫描两次
• 空间复杂度：O(N)