3. 无重复字符的最长子串
3. 无重复字符的最长子串
🟠 🔖 哈希表
字符串
滑动窗口
🔗 力扣
LeetCode
题目
Given a string s
, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 10^4
s
consists of English letters, digits, symbols and spaces.
题目大意
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
子字符串 是字符串中连续的 非空 字符序列。
解题思路
这一题可以使用 滑动窗口 技巧来解决。
定义滑动窗口:
- 使用两个指针
left
和right
来表示滑动窗口的左右边界。滑动窗口会随着指针的移动而扩大或收缩。 - 维护一个
window
对象,记录当前窗口中各字符出现的频次。
- 使用两个指针
扩展右指针:
- 每次将右指针
right
向右移动一格,将对应的字符加入window
,更新该字符的出现次数。
- 每次将右指针
收缩左指针:
- 如果当前字符已经在窗口中出现了不止一次(即
window[c] > 1
),说明当前窗口中有重复字符。此时我们要通过移动左指针left
来缩小窗口,直到去掉重复的字符,保证窗口内每个字符只出现一次。
- 如果当前字符已经在窗口中出现了不止一次(即
记录结果:
- 每次调整完窗口后,检查当前窗口的大小,并更新最长子串的长度
res
。
- 每次调整完窗口后,检查当前窗口的大小,并更新最长子串的长度
终止条件:
- 当右指针遍历到字符串的末尾时,循环结束,返回
res
即为最长不含重复字符的子串长度。
- 当右指针遍历到字符串的末尾时,循环结束,返回
详细的滑动窗口答题框架讲解,可阅读 《3.11 滑动窗口》。
复杂度分析
时间复杂度:
O(n)
,其中n
是字符串s
的长度。- 外层的
while
循环遍历字符串s
,每个字符最多只会被左指针和右指针访问一次。因此,整个滑动窗口算法的时间复杂度为O(n)
,因为每个字符至多只会被访问两次(一次右指针移动,一次左指针移动)。 - 更新
window
和比较操作都是常数时间操作O(1)
,不会影响整体复杂度。
- 外层的
空间复杂度:
O(1)
- 虽然在
window
中存储字符的频次,但window
最多只会包含 128 个 ASCII 字符,因此空间复杂度为O(1)
,与字符串s
的长度无关。 - 其他变量如
left
、right
、res
以及中间变量c
和d
都只占用常数空间。
- 虽然在
代码
滑动窗口框架
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let window = {}, // 记录窗口内字符的频次
left = 0, // 左指针
right = 0, // 右指针
res = 0; // 记录最长子串的长度
// 遍历字符串
while (right < s.length) {
let c = s[right]; // 当前右指针指向的字符
right++; // 右指针向右移动
window[c] = (window[c] || 0) + 1; // 统计当前字符的频次
// 如果窗口内有重复字符,收缩窗口
while (window[c] > 1) {
let d = s[left]; // 左指针指向的字符
left++; // 左指针向右移动,缩小窗口
window[d]--; // 减少窗口内字符频次
}
// 更新结果,记录最大长度
res = Math.max(res, right - left);
}
return res; // 返回最长不含重复字符的子串长度
};
简化版
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let max = 0;
let curStr = '';
for (let i = 0; i < s.length; i++) {
const char = s.charAt(i);
const pos = curStr.indexOf(char);
if (pos !== -1) {
curStr = curStr.slice(pos + 1, curStr.length);
}
curStr += char;
max = Math.max(max, curStr.length);
}
return max;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
159 | 至多包含两个不同字符的最长子串 🔒 | 哈希表 字符串 滑动窗口 | 🟠 | 🀄️ 🔗 | |
340 | 至多包含 K 个不同字符的最长子串 🔒 | 哈希表 字符串 滑动窗口 | 🟠 | 🀄️ 🔗 | |
992 | K 个不同整数的子数组 | 数组 哈希表 计数 1+ | 🔴 | 🀄️ 🔗 | |
1695 | 删除子数组的最大得分 | 数组 哈希表 滑动窗口 | 🟠 | 🀄️ 🔗 | |
2067 | 等计数子串的数量 🔒 | 字符串 计数 前缀和 | 🟠 | 🀄️ 🔗 | |
2260 | 必须拿起的最小连续卡牌数 | [✓] | 数组 哈希表 滑动窗口 | 🟠 | 🀄️ 🔗 |
2401 | 最长优雅子数组 | 位运算 数组 滑动窗口 | 🟠 | 🀄️ 🔗 | |
2405 | 子字符串的最优划分 | 贪心 哈希表 字符串 | 🟠 | 🀄️ 🔗 | |
2799 | 统计完全子数组的数目 | 数组 哈希表 滑动窗口 | 🟠 | 🀄️ 🔗 | |
2981 | 找出出现至少三次的最长特殊子字符串 I | 哈希表 字符串 二分查找 2+ | 🟠 | 🀄️ 🔗 | |
2982 | 找出出现至少三次的最长特殊子字符串 II | 哈希表 字符串 二分查找 2+ | 🟠 | 🀄️ 🔗 |