3. 无重复字符的最长子串
给定一个字符串 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
由英文字母、数字、符号和空格组成
方法一:双指针 + HashMap
定义一个哈希表记录当前窗口内出现的字符,记 ans
。
遍历字符串 s
的每个字符 c
,循环结束。将 c
加入哈希表中,此时 ans
的最大值。
最后返回 ans
即可。
时间复杂度 s
的长度。
双指针算法模板:
java
for (int i = 0, j = 0; i < n; ++i) {
while (j < i && check(j, i)) {
++j;
}
// 具体问题的逻辑
}
java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符 c 出现过,并且在当前窗口内
if (map.containsKey(c) && map.get(c) >= left) {
left = map.get(c) + 1; // 把 left 移动到重复字符之后
}
map.put(c, right); // 更新字符 c 的最新位置
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
bool ss[128]{};
int ans = 0;
for (int i = 0, j = 0; j < s.size(); ++j) {
while (ss[s[j]]) {
ss[s[i++]] = false;
}
ss[s[j]] = true;
ans = max(ans, j - i + 1);
}
return ans;
}
};
ts
function lengthOfLongestSubstring(s: string): number {
let ans = 0;
const ss: Set<string> = new Set();
for (let i = 0, j = 0; j < s.length; ++j) {
while (ss.has(s[j])) {
ss.delete(s[i++]);
}
ss.add(s[j]);
ans = Math.max(ans, j - i + 1);
}
return ans;
}
python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ss = set()
ans = i = 0
for j, c in enumerate(s):
while c in ss:
ss.remove(s[i])
i += 1
ss.add(c)
ans = max(ans, j - i + 1)
return ans
方法二:双指针 + HashSet
java
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, ans = 0;
Set<Character> set = new HashSet<>();
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果出现重复字符,就移动左边界
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}