zhangdi

3.无重复字符的最长子串 ​

题目 ​

LeetCode 中等

题目

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

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

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

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

题解 ​

方法：Set + 双指针 + 滑动窗口 ​

双指针 滑动窗口 Set

O(n) O(set 长度)

ts
function lengthOfLongestSubstring(s: string): number {
  const sLen = s.length
  if (sLen < 2) return sLen
  const tempSet = new Set()
  let maxLen = 0
  let l = 0
  for (let r = 0; r < sLen; r++) {
    const cur = s[r]
    console.log(r, cur)

    //从左指针的字符开始删，一直删到Set里没有当前字符
    while (tempSet.has(cur)) {
      const lStr = s[l]
      console.log('左指针：', l, lStr)
      tempSet.delete(lStr)
      ++l
    }

    tempSet.add(cur)
    maxLen = Math.max(maxLen, tempSet.size)

    console.log('左指针：', l, '，最长：', maxLen)
    console.log(tempSet)
  }
  return maxLen
}

console.log('🌰', lengthOfLongestSubstring('pwwkew'))

方法：Map + 双指针 + 滑动窗口 ​

双指针 滑动窗口 Map

O(n) O(map 长度)

ts
function lengthOfLongestSubstringUseMap(s: string): number {
  const sLen = s.length
  const map = new Map()
  let maxLen = 0
  let l = 0
  for (let r = 0; r < sLen; r++) {
    const cur = s[r]
    console.log(r, cur)

    //map记录每个字符最新的位置，左指针可以直接指向后一位，不需要向上面Set那样循环删除
    if (map.has(cur) && map.get(cur) >= l) {
      l = map.get(cur) + 1
    }
    map.set(cur, r)

    maxLen = Math.max(maxLen, r - l + 1)

    console.log('左指针：', l, '，最长：', maxLen)
    console.log(map)
  }
  return maxLen
}

console.log('🌰', lengthOfLongestSubstringUseMap('abcabcbb'))