- LeetCode 热题 100 - 两数之和
- 字母异位词分组
- 最长连续序列
- 移动零
- 盛最多水的容器
- 三数之和
- 接雨水
- 找到字符串中所有字母异位词
- 无重复字符的最长子串
- 和为 K 的子数组
- 滑动窗口最大值
无重复字符的最长子串
class 哈希表,字符串,滑动窗口给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
解法一:
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (!s) {
return 0;
}
if (s.length === 1) {
return 1;
}
let set = new Set();
let left = 0;
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
while (set.has(s[i])) {
set.delete(s[left]);
left++;
}
set.add(s[i]);
maxLength = Math.max(maxLength, i - left + 1);
}
return maxLength;
};
要找到字符串 s
中不含重复字符的最长子串的长度,我们可以使用滑动窗口技术结合哈希表来实现。这种方法可以在一次遍历中解决问题,从而高效地找到最长的无重复字符子串。
方法:滑动窗口
算法步骤
初始化变量:
使用一个哈希集合
char_set
来存储当前窗口中不重复的字符。使用两个指针
left
和right
表示滑动窗口的左右边界,初始值为 0。初始化
max_length
为 0,用于存储最长无重复字符子串的长度。滑动窗口遍历字符串:
如果
s[right]
不在char_set
中:如果
s[right]
在char_set
中:将
s[right]
加入char_set
。更新
max_length
为max(max_length, right - left + 1)
。从
char_set
中移除s[left]
,并将left
指针右移,直到s[right]
不在char_set
中。使用
right
指针遍历字符串s
。对于每个字符
s[right]
,检查其是否在char_set
中。将当前字符
s[right]
加入char_set
,继续移动right
指针。返回结果:
遍历结束后,
max_length
即为最长无重复字符子串的长度。
算法实现
下面是用 Python 实现的代码:
def length_of_longest_substring(s):
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
# 示例
s = "abcabcbb"
result = length_of_longest_substring(s)
print("最长无重复字符子串的长度:", result)
示例
输入:
s = "abcabcbb"
输出:
3
解释
在这个例子中,最长无重复字符子串为 "abc"
,其长度为 3
。
复杂度分析
时间复杂度:O(n),其中 n 是字符串
s
的长度。每个字符在滑动窗口的左右指针之间最多被访问两次。空间复杂度:O(min(n, m)),其中 n 是字符串
s
的长度,m 是字符集的大小。使用哈希集合来存储字符。
这种方法通过滑动窗口有效地在 O(n) 时间内解决了最长无重复字符子串的问题,是解决此类问题的常用技巧。