1. 题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

2. 解题思路

这个题目可以使用双指针+map来实现：

  • 首先用双指针维护一个滑动窗口用来剪切子串
  • 开始时，两个指针都在起始位置，不断移动右指针，遇到重复的字符，就将左指针向后移动一位
  • 右指针每次移动，都计算出两个指针之间的字符个数，并返回最大值
  • 每次右指针移动还需要将右指针的索引和值存在Map中，便于后面遇到重复值时让左指针进行移动

需要注意的是，在左指针移动之后，map中还存在其之前的值，所以还要限制map中已经存在的值的索引要大于左指针的索引，也就是必须处于两指针之间的滑动窗口。

该算法的时间复杂度为O(n)，空间复杂度为O(m)，其中m是最长子串的长度。

3. 代码实现

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var lengthOfLongestSubstring = function(s) {
  6.     let res = 0
  7.     let map = {}
  9.     for(let left = 0, right = 0; right < s.length; right++){
  10.         const char = s[right]
  11.         if(map[char] >= 0 && map[char] >= left){
  12.             left = map[char] + 1
  13.         }
  14.         res = Math.max(res, right - left + 1)
  15.         map[char] = right
  16.     }
  17.     return res
  18. };

4. 提交结果

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