题目

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

示例 1:

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

示例 2:

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

示例 3:

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

解法

双指针法

假设两个指针，一个标记开始索引，一个标记结束索引，同时准备一个遍历过的字符的HASH表。

指针均从0位开始，结束索引遇到一个字符分为两个情况：

  1. 该字符不在HASH表中：HASH表中加入这个字符的索引，同时结束索引继续往后遍历
  2. 该字符在HASH表中：
    • 开始索引大于该字符的索引：结束索引继续往后遍历就行
    • 开始索引小于等于该字符的索引：更新该字符的索引，同时开始索引变为该字符索引+1,结束索引+1
  • 时间复杂度：$O(n)=n$
  • 空间复杂度：$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        startIdx = 0
        endIdx = 0
        maxL = 0
        for i in s:
            if i in d and d[i] >= startIdx:
                startIdx = d[i] + 1
            d[i] = endIdx
            endIdx += 1
            maxL = maxL if maxL > endIdx - startIdx else endIdx - startIdx
        return maxL

# runtime:52 ms
# memory:13.4 MB