滑动窗口

无重复字符的最长子串

返回长度

function lengthOfLongestSubstring(string) {
  const charSet = new Set() // 当前的滑动窗口
  let left = 0 // 当前无重复子串的起始索引(滑动窗口左边)
  let maxLength = 0 // 最长无重复子串的长度

  for (let right = 0; right < string.length; right++) {
    const rightChar = string.charAt(right)
    while (charSet.has(rightChar)) {
      charSet.delete(string.charAt(left))
      left++
    }
    charSet.add(rightChar)
    maxLength = Math.max(maxLength, charSet.size)
  }
  return maxLength
}

1. 使用一个 Set 来记录当前窗口中的字符。
2. 使用两个指针 left 和 right 代表当前窗口的左右边界。
3. 滑动窗口,当遇到重复字符时，移动 left 指针并从集合中移除字符，直到窗口中没有重复字符,加入右边的字符。
4. 每次更新最大长度。

这道题要求返回最大长度.滑动窗口(set)并不代表当前最大的长度,所以每次要对比当前窗口的长度与最大长度,取最大值.

返回子串

function lengthOfLongestSubstring(string) {
  const charSet = new Set()
  let left = 0
  let maxLength = 0
  let longestStartIdx = 0 // 最长无重复子串的起始索引

  for (let right = 0; right < string.length; right++) {
    const rightChar = string.charAt(right)
    while (charSet.has(rightChar)) {
      charSet.delete(string.charAt(left))
      left++
    }
    charSet.add(rightChar)

    if (charSet.size > maxLength) {
      maxLength = charSet.size
      longestStartIdx = left
    }
  }

  return string.slice(longestStartIdx, longestStartIdx + maxLength)
}

不同点:

• 需要返回整个子串.所以要增加变量,longestStartIdx记录子串起始位置.

• 每次移动时判断当前的窗口长度是否大于最大长度,如果大于,则更新最大长度和子串起始位置.