题目

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

示例 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