3.无重复字符的最长子串

题目描述

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

Given a string s, find the length of the longest substring without repeating characters.

示例  1:

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

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

解题方法

方法一：滑动窗口 - 数组

• 思路：

  • 使用数组来维护滑动窗口，窗口内是无重复的元素

• 步骤：

  • 遍历字符串，判断字符是否在滑动窗口数组中
    • 在：删除滑动窗口数组中相同字符以及相同字符前的所有字符，再将当前字符push到滑动窗口数组中
    • 不在：直接将元素push进入滑动窗口数组中
    • 比较当前滑动窗口数组的长度和之前滑动窗口数组长度的最大值
  • 返回滑动窗口数组长度最大值

• 复杂度分析：

  • 时间复杂度：O(n^2), for循环 时间复杂度为 O(n)，indexOf()和 splice() 时间复杂度为 O(n)
  • 空间复杂度：O(m)，滑动窗口数组的长度

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const arr = [];
  let max = 0;
  for (let i = 0; i < s.length; i += 1) {
    const idx = arr.indexOf(s[i]);
    if (idx !== -1) {
      arr.splice(0, idx + 1);
    }
    arr.push(s[i]);
    max = Math.max(arr.length, max);
  }
  return max;
};

方法二：滑动窗口 - 双指针

• 思路：

  • 使用双指针来维护滑动窗口，窗口内是无重复的元素

• 步骤：

  • 遍历字符串，右指针向右移动，判断字符是否在窗口中
    • 在：先判断重复字符的位置是否在左指针左边，若不在，则左指针向右移动至重复字符的下一位（收敛左边界的前提是重复元素在左右指针的区间内），窗口加入新字符
    • 不在，窗口加入新字符
    • 比较当前滑动窗口的最大值，之前的最大值和右指针 - 左指针 + 1即当前滑动窗口区间长度进行比较
  • 返回滑动窗口长度最大值

• 复杂度分析：

  • O(N)，一个 for 循环，map 为 O(1)
  • O(M)，M 为滑动窗口中字符个数

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let l = 0;
  let max = 0;
  const map = new Map();
  for (let r = 0; r < s.length; r += 1) {
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1;
    }
    max = Math.max(r - l + 1, max);
    map.set(s[r], r);
  }
  return max;
};