题目描述

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

解题思路

image.png

  • 先找出所有不包含重复字符的字串，这个是本题的难点和突破口。
  • 找出长度最大的那个字串，即为结果。

解题步骤

  • 用双指针维护一个滑动窗口，用来剪切字串。
    • 双指针： 两个变量来记录子串的起始位置和结束位置，它们可以维护一个滑动窗口
    • 滑动窗口：在一些音视频剪切软件上，通常都有一个滑动窗口，拖动窗口的左右边框改变窗口大小来剪切音视频。我们剪切字符串也是这样的，包括我们JavaScript的求子串的方法slice也是一个滑动窗口。简而言之即为所要剪切字符串的起始位置和结束位置。
  • 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。
  • 过程中记录所有窗口的长度，并返回最大值

代码实现

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var lengthOfLongestSubstring = function (s) {
  6.     let left = 0
  7.     let res = 0
  8.     const map = new Map()
  9.     const len = s.length
  10.     for (let right = 0; right < len; right++) {
  11.         if (map.has(s[right]) && map.get(s[right]) >= left) { //map.get(s[right]) >= left 重复下标必须在滑动窗口里面，left即为滑动窗口起始位置 
  12.             left = map.get(s[right]) + 1
  13.         }
  14.         res = Math.max(res, right - left + 1) // 与原res进行长度的对比并将最大值更新给res
  15.         map.set(s[right], right) // 记录下标
  16.     }
  17.     return res
  18. };

时间复杂度O(n)
空间复杂度O(m)， m为字符串中不重复字符的个数