滑动窗口｜双指针｜3. 无重复字符的最长子串

2021 年 06 月 23 日 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目

描述

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

  示例

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

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

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

示例 4:
输入: s = “”
输出: 0

提示

• 0 <= s.length <= 5 * 10

• s 由英文字母、数字、符号和空格组成

  解答

• 设置 minIndex 作为左指针，指向不重复的字符串的首字符

• 设置 maxLength 用于记录不重复字符串的最大长度，因为当前不重复字符串可能不是最大字符串，所以需要用 maxLength 记录
• 遍历字符串，i 作为遍历索引也作为右指针
• 设置 map 存放遍历过程中的每个字符，以当前字符作为 key，当前索引作为 i。如果遇到重复字符则更新
  • 用此种规则存放字符，如果出现重复字符则会更新，比如字符串 “abcba”，当 i === 3 时 map 中的 “key = b” 的值就会从 1 更新到 3
  • 同时 map 中还会存放着垃圾数据，比如字符串 “abcba”，当 i === 3 时 map 中的 “key = b” 的值更新为了 3，此时说明窗口已经滑动到了 “c” 字符的位置，所以此时 map 中的 “key = a” 则为无效字符；当 i === 4 时当前字符为 “a” 此时查询 map 能查到对应的字符 “key = a” 但是因为它已经是无效字符，所以此时的“a”不是重复字符，因此需要 minIndex 来控制窗口左边位置，当从 map 中查询到的字符时，此字符对应的索引 value 只有在 minIndex 要求的范围内，才算重复字符
• 设置 curIndex 存放当前项 map 中取出的值
• 遍历过程中，如果 curIndex >= minIndex 代表当前字符已经出现过，并且在窗口内，则证明此时发生了重复，所以可以将左指针移向与当前位置重复的位置的下一个位置，比如字符串 “abcba”，当 i===3 时，与 i===1 的位置重复了，此时将左指针移动到 i===2 的位置
• 当前不重复字符串的长度等于当前索引 i + 1 - minIndex，如果当前长度比历史的最大长度长，则更新历史的最大长度

  /**
  * @param {string} s
  * @return {number}
  */
  var lengthOfLongestSubstring = function(s) {
      // 字符字典
    const dic = new Map()
    // 左指针
    let minIndex = 0
    // 历史最大长度
    let maxLength = 0
    // 当前字符在 map 中存放的索引
    // 即当前字符上次出现的索引
    let curIndex
    for(let i = 0; i < s.length; i ++){
        curIndex = dic.get(s[i])
          // 如果上次出现的索引比左指针大，则证明字符重复发生在窗口内，重复有效
        if(curIndex >= minIndex){
              // 将左指针移动到上此出现的索引的下一位，缩小当前窗口
            minIndex = curIndex + 1
        }
          // 将当前字符存放到 map 中，并记录最新索引
        dic.set(s[i], i)
          // 将当前统计的不重复字符串的长度与历史不重复字符串的长度对比，存储最大值
        maxLength = Math.max(i + 1 - minIndex, maxLength)
    }
    return maxLength
  };