算法
- 维护一个滑动窗口：
- 滑动窗口用两个指针表示，
j 为窗口左端，i 为窗口右端
- 窗口内的子串为
[j, i]，保证该窗口内没有重复字符
- 使用哈希表记录字符出现的次数：
- 哈希表
hash 的 key 为字符，value 为该字符在窗口中的出现次数
- 移动窗口右端：
- 遍历字符串，右端指针
i 每次右移一格，将字符加入窗口并更新哈希表
- 处理重复字符：
- 如果窗口中出现重复字符（即当前字符的出现次数大于 1），移动左端指针
j，并在哈希表中移除字符，直到窗口内没有重复字符。
- 更新结果：
- 每次移动窗口时，计算当前窗口的长度
(i - j + 1)，并更新结果 res
复杂度分析
时间复杂度
每个字符至多被访问两次（右指针扩展时访问一次，左指针收缩时访问一次），时间复杂度为 O(n)
空间复杂度
使用哈希表存储字符出现次数，空间复杂度为 O(k)，其中 k 为字符集大小
C++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
std::unordered_map<char, int> hash; // 记录字符出现次数
int res = 0; // 最长子串长度
for (int i = 0, j = 0; i < s.size(); ++ i)
{
++hash[s[i]]; // 将字符加入窗口
// 如果出现重复字符，移动左指针 j
while (hash[s[i]] > 1)
{
-- hash[s[j]];
++ j;
}
// 更新最长子串长度
res = std::max(res, i - j + 1);
}
return res;
}
};
|
Python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
freq = {}
j = 0
for i, ch in enumerate(s):
if ch not in freq:
freq[ch] = 0
freq[ch] += 1
while freq[ch] > 1:
freq[s[j]] -= 1
j += 1
res = max(res, i - j + 1)
return res
|
Go 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func lengthOfLongestSubstring(s string) int {
freq := make(map[byte]int)
res, j := 0, 0
for i := 0; i < len(s); i ++ {
freq[s[i]] ++
for freq[s[i]] > 1 {
freq[s[j]] --
j ++
}
res = max(res, i - j + 1)
}
return res
}
|
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let res = 0;
let freq = new Map();
for (let i = 0, j = 0; i < s.length; i++) {
freq.set(s[i], (freq.get(s[i]) || 0) + 1);
while (freq.get(s[i]) > 1) {
freq.set(s[j], freq.get(s[j]) - 1);
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
};
|
