一：题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
二：示例与提示
示例 1:
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
提示：
0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成
三：思路
暴力求解法
- 两层循环遍历字符串，找到所有的子串可能，返回子串长度
- 外层循环表示子串起始位置
- 内层循环J表示子串结束位置
- 利用set数据结构创造set集合，不断添加s[j]，元素，当未遇到set集合中有的，即是满足条件的子串，计算子串的最大长度
- 当遇到集合中有的直接break内层循环
滑动窗口
- 不断调整子序列的起始位置和终止位置，从而得到我们想要的结果
- 用一个for循环就达到了两层循环的效果
- for循环应表示的是滑动窗口的终止位置
- 如果表示的是滑动窗口的起始位置，那么还需要一个变量去不断地向右去遍历，这样的逻辑与暴力求解没什么区别，所以不行
- 利用一个左指针i去表示子序列的起始位置
- 当遇到重复子串，就应该缩小窗口，即左指针向右移动
- 右指针有循环控制着，窗口扩大
- 缩小窗口，是先删除左指针的元素，再将左指针右移
四：代码 + 复杂度分析
暴力求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
var lengthOfLongestSubstring = function(s) {
if(s.length === 0) return false
let result = -Infinity
for(let i = 0; i < s.length; i++) {
const set = new Set()
for(let j = i; j < s.length; j++) {
let char = s.charAt(j)
if(!set.has(char)){
result = Math.max(result, j - i + 1)
}else {
break
}
set.add(char)
}
}
return result
};
|
时间复杂度：
- 最坏时间复杂度为O（n ^ 2）
- 外层循环遍历整个字符串为n
- 内层循环表示从当前字符位置向右遍历整个字符串，最坏程度为n，即未遇到重复字符
- 但一般会遇到重复字符，所以内层循环一般遍历n / 2
- 平均时间复杂度为 O ( n * n / 2) -> O (n ^ 2 / 2) -> O (n ^ 2)
空间复杂度：O（n）
- 在每次内层循环中，都会创建一个新的Set集合来存储字符，最坏情况下会创建n个字符实例
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
var lengthOfLongestSubstring = function(s) {
if(s.length === 0) return 0
let left = 0
let result = -Infinity
const set = new Set()
for(let right = 0; right < s.length; right++) {
let char = s.charAt(right)
while(set.has(char)) {
set.delete(s[left])
left++
}
set.add(char)
result = Math.max(result, right - left + 1)
console.log(result)
console.log(s[right])
}
return result
};
|
- 时间复杂度：O（n）
- 外层循环（
for 循环）会执行 n 次，其中 n 是输入字符串 s 的长度。
- 内层循环（
while 循环）的执行次数并不会累积到 n^2。虽然内层循环看起来是一个循环嵌套在另一个循环中，但每个字符只会被 left 指针移动一次。一旦字符在内层循环中被处理过，它不会再次被处理。因此，内层循环的总执行次数是 n，而不是 n^2。
- 空间复杂度：O（n）
