# 3.无重复字符的最长子串
# 题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3
2
3
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3
2
3
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
2
3
4
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// do some things ...
};
1
2
3
4
5
6
7
2
3
4
5
6
7
# 错解
# 错解一：认为子串分区是不重叠的
# 思路
不含有重复字符的最长子串的长度
即从开始记录不重复的字串，遇到重复的之后去验证是否满足最长字串，满足则替换，不满足向下寻找新的子串。分区如图：
# 代码
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
// string to Array
var strArray = s.split("");
// create Set
var tmpSet = new Set();
var maxnum = s.length ? 1 : 0;
strArray.map((item, index) => {
if (tmpSet.has(item)) {
maxnum = tmpSet.size > maxnum ? tmpSet.size : maxnum;
tmpSet.clear();
}
tmpSet.add(item);
});
maxnum = tmpSet.size > maxnum ? tmpSet.size : maxnum;
return maxnum;
};
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
经测试：
"dvdf" 未通过测试，期望得到3，结果是2
因为我们在这个思路下的子串是这样寻找的 dv 和 df
这样的思路本身没有问题，但是对于子串的分布应该如下图才对：
# 题解
# 解法一：暴力破解法
# 思路
每个字符开始作为一个子串，即遍历字符串数组，每当完成一个字符开头的无重复字符的时候，跳出该子串，进行 shift 操作，开始下一个子串的遍历，记录并统计后与最大值比对替换，最终返回最大值。
超长字符串会超时。 所以不做展示，固定数量短一些的字符串可行。
# 解法二：特殊组合法
如下图所示，遇到含有next或prev的相冲重复数值时候，记为特殊组合，最长特殊组合的length（7 - 3 = 4） 就是需要的结果，可通过Math.max得到。
这种方式需要将每一个字符都开始向后处理一遍，时间复杂度同样过高，但可解。
# 解法三：滑动窗口
# 思路
将字符串遍历一遍，记录对应过程的子串
- 当该值在记录的值中未重复的时候,记算最大的结果并记录；
- 当该值在记录的值中已重复的时候,将该值加入，并剔除重复值之前的字符。num记作新的子串长度。
- 向下循环
# 代码
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let num = 0, res = 0;
let m = '';
for (n of s) {
if (m.indexOf(n) == -1) {
m += n;
num++;
res = res < num ? num : res;
} else {
m += n;
m = m.slice(m.indexOf(n) + 1);
num = m.length;
}
};
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
感谢 Heternally-老三 的代码，带着我爬出坑。
# 致谢
感谢大家阅读我的文章，如果对我感兴趣可以点击页面右上角，帮我点个star。
作者：前端小然子
链接： https://xiaoranzife.com/guide/arithmetic/3.lengthOfLongestSubstring.html
来源：前端小然子的博客
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
← 2.两数相加