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

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

// 解题思路
// 1，先找出所有的不包含重复字符的子串
// 2，找出长度最大那个子串，返回其长度即可

// 解题步骤
// 1，用双指针维护一个滑动窗口，用来剪切子串
// 2，不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
// 3，过程中，记录所有窗口的长度，并返回最大值
// 4，赶紧关注我的微信公众号获取更多内容吧：手摸手前端进阶  

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let l = 0 // 左指针
  let res = 0 // 声明res 记录最大值
  const map = new Map()
  for (let r = 0; r < s.length; r++) {  // 右指针滑动遍历
    if (map.has(s[r]) && map.get(s[r]) >= l) { 
        // map.get(s[r]) >= l 尾元素与首元素相同的情况
      l = map.get(s[r]) + 1
    }
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }
  return res
};

// 时间复杂度：O(n)
// 空间复杂度：O(m),m是字符串中不重复字符的个数

// 题目转载自力扣官网：
// https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
复制代码