# 无重复字符的最长子串
# 难度：中等
# 描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
# 样例：
- 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
- 输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
- 输入: "dvdf"
输出: 3
解释: 因为无重复字符的最长子串是 "vdf"，所以其长度为 3。
- 输入: "asjrgapa"
输出: 6
解释: 因为无重复字符的最长子串是 "sjrgap"，所以其长度为 6。
- 输入: "aabaab!bb"
输出: 3
解释: 因为无重复字符的最长子串是 "ab!"，所以其长度为 3。
- 输入: "abcb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 输入: "asljlj"
输出: 4
解释: 因为无重复字符的最长子串是 "aslj"，所以其长度为 4。
- 输入: "qwnfenpglqdq"
输出: 8
解释: 因为无重复字符的最长子串是 "fenpglqd"，所以其长度为 8。
# 思路分析：
关键在于在出现重复字符时，如何更新不重复字符的index
# 代码模板：
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
}
1
2
3
4
5
6
2
3
4
5
6
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
- 用对象储存字符的位置, 出现重复字符时更新不重复字符的index。
var lengthOfLongestSubstring = function (s) {
let obj = {}; // 用于储存字符出现的位置
let res = 0; // 最大值
let j = 0; // 不重复字符的index
for (let i = 0; i < s.length; i++) {
// 当前值是否在对象中存储过
const value = obj[s[i]]
if (value !== undefined) {
// 更新上一次重复值的index
// value + 1 跳过之前重复的字符
// j: 之前不重复的index 重复字符 需要全部跳过
j = Math.max(value + 1, j)
}
// 每个字符都计算一下最长不重复值 保存最大值
// 不重复最长长度 = 当前index - 上一次重复值的index + index从0开始 长度从1开始
res = Math.max(res, i - j + 1);
// 存/更新 字符串index
obj[s[i]] = i
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- 从左到右，一个字符一个字符搜索，看是否重复。
var lengthOfLongestSubstring = function (s) {
var i = 0, // 不重复字符的index
res = 0; // 更新无重复字符的长度
for (j = 0; j < s.length; j++) {
// 查找：不重复字符-当前index之间 有没有出现当前字符
let index = s.slice(i, j).indexOf(s[j])
if (index === -1) {
// 更新无重复字符的长度：当前index-不重复字符的index + 长度从1开始算
res = Math.max(res, j - i + 1);
} else {
// 更新i = 不重复字符的index
// 不重复字符的index = 原不重复的字符index + i-j中出现重复字符的index + 跳过该重复字符
i = i + index + 1;
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17