题目地址(0003. 无重复字符的最长子串)
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
核心知识
- 滑动窗口
- 哈希表
JS实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
var lengthOfLongestSubstring = function (s) {
let start = 0,
end = 0,
freqMap = {},
maxLen = 0;
while (end < s.length) {
if (freqMap[s[end]] === undefined) {
freqMap[s[end]] = 1;
maxLen = Math.max(maxLen, end - start + 1);
end++;
} else {
delete freqMap[s[start]];
start++;
}
}
return maxLen;
};
|
废话
使用map确认是否有重复字符，滑动窗口记录当前最长的无重复子串. 在移除的过程中还是很挫，因为获得重复索引的话，start是可以直接一步跳到位的，而不必做无用的累加，但基于map的确认，还是需要逐个从map中移除.若使用数组的话，又会添加确认重复的检索负担