无重复字符的最长子串¶
标签：Hash Table, Two Pointers, String, Sliding Window
描述¶
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题解¶
滑动窗口¶
使用滑动窗口法，配合两个指针(left, right)和哈希表进行求解。ASCII含128个字符，将每个字符出现在字符串中的最新位置存入哈希表hash[s[right]]。当出现重复字符后，右指针right可以通过哈希表检索到重复字符之前出现的位置，前后两个重复字符位置之间的距离right-left就是不重复字符的长度，如果该长度大于当前存储的最长子串则更新长度。
int lengthOfLongestSubstring(char * s){
int res = 0, tmp = 1;
int left = 0, right = 1; // 左右指针
int hash[128] = {0}; // 每个字符的出现位置
int pos = 0; // 重复字符的前一次出现位置索引
int len = strlen(s);
if (len <= 1)
return len;
memset(hash, -1, sizeof(hash)); // -1 代表未出现过
hash[s[0]] = 0;
while(right < len) {
pos = hash[s[right]];
if (pos != -1 && pos >= left) {
tmp = right - left;
if (tmp > res)
res = tmp;
left = pos + 1;
tmp = right - left + 1;
}
else {
tmp++;
if (tmp > res)
res = tmp;
}
hash[s[right]] = right;
right++;
}
return res;
}
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
right = 0
substr = set()
n = len(s)
for left in range(n):
if left != 0:
substr.remove(s[left - 1])
while right < n and s[right] not in substr:
substr.add(s[right])
right+=1
res = max(res, right - left)
return res
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
left = -1
substr = {}
for right, num in enumerate(s):
if num in substr and substr[num] > left:
left = substr[num]
substr[num] = right
if right - left > res:
res = right - left
return res
- 时间复杂度： \(O(N)\) , N 为字符串长度
- 空间复杂度： \(O(|Σ|)\) , \(|Σ|\) 代表字符集的大小
优化¶
上面的C代码还有优化空间，优化代码：
- 用memset初始化哈希表，只要把字符对应的hash值加1即可，恰好对应字符的物理位置(1,2,3,...).
- 不必考虑字符串长度
len, 将while循环的结束条件改为遇到字符\0. - 将
res更名为max, 代表最长子串长度；将tmp更名为cnt, 代表当前不重复子串的长度计数.
int lengthOfLongestSubstring(char * s){
int max = 0, cnt = 0;
int left = 0, right = 0; // 滑动窗口的左右指针
int hash[128] = {0}; // 哈希表，存储每个字符出现的最新位置
int pos = 0; // 重复字符的位置
while(s[right] != '\0') {
pos = hash[s[right]];
if (pos > left) {
cnt = right - left;
if (cnt > max)
max = cnt;
left = pos;
cnt = right - left + 1;
}
else {
cnt++;
if (cnt > max)
max = cnt;
}
hash[s[right]] = right + 1;
right++;
}
return max;
}
注意
值得注意的是，在if语句中，由于哈希值不是字符的索引值，而是加1后的物理位置，所以给left赋值无需加1.
到这里，还可以继续优化，上面的if else有两个分支，实际上可以只用一个.cnt不用频繁更新，只需要在遇到重复字符的时候更新，不过还要考虑最后一个字符不是重复字符的情况，所以返回前需要再计算一次。
此外，while循环也可以改为for循环，注意去掉right++以避免重复。
int lengthOfLongestSubstring(char * s){
int max = 0, cnt = 0;
int left = 0, right = 0; // 滑动窗口的左右指针
int hash[128] = {0}; // 哈希表，存储每个字符出现的最新位置
int pos = 0; // 重复字符的位置
for(right = 0; s[right]!='\0'; right++) {
pos = hash[s[right]];
if (pos > left) {
cnt = right - left;
max = cnt>max?cnt:max;
left = pos;
}
hash[s[right]] = right + 1;
}
cnt = right - left;
return cnt>max?cnt:max;
}
举例¶
以字符串"abcdefaghja"为例，使用优化后的C程序。这里共有3个重复的a，不重复最长子串是"bcdefaghj"
0 1 2 3 4 5 6 7 8 9 10
a b c d e f a g h j a
^
lr
# 更新 hash['a'] = hash[s[right]] = right + 1 = 1
# 移动右指针 right
a b c d e f a g h j a
^ ^
l r
a b c d e f a g h j a
^ ^
l r
...
a b c d e f a g h j a
^ ^
l r
# 遇到重复字符 'a'，cnt = right - left = 6 - 0 = 6
# max = cnt>max?cnt:max = cnt = 6
# 更新 left = hash[s[right]] = hash['a'] = 1 (重复字符前一次出现位置 + 1)
# 更新后左右指针如下
a b c d e f a g h j a
^ ^
l r
# 更新 hash['a'] = hash[s[right]] = right + 1 = 7
# 继续移动右指针
a b c d e f a g h j a
^ ^
l r
...
a b c d e f a g h j a
^ ^
l r
# 再次遇到重复字符 'a'
# cnt = right - left = 10 - 1 = 9
# max = cnt>max?cnt:max = cnt = 9
# 更新 left = hash[s[right]] = hash['a'] = 7 (重复字符前一次出现位置 + 1)
# 更新后左右指针如下
a b c d e f a g h j a
^ ^
l r
# 到达结束符, right = 11, cnt = right - left = 11 - 7 = 4
# max = cnt>max?cnt:max = cnt = 9
小结¶
- 滑动窗口特别适合字符串子串的处理
- 哈希表用于记录字符索引非常方便
- 要多多考虑边界问题的处理