JS⽆重复字符的最长⼦串（⼒扣++）
给定⼀个字符串 s ，请你出其中不含有重复字符的 最长⼦串 的长度。
⽰例 1:
输⼊: s ="abcabcbb"
输出:3
解释：因为⽆重复字符的最长⼦串是"abc"，所以其长度为3。
⽰例 2:
输⼊: s ="bbbbb"
输出:1
解释：因为⽆重复字符的最长⼦串是"b"，所以其长度为1。
⽰例3:
输⼊: s ="pwwkew"
输出:3
解释：因为⽆重复字符的最长⼦串是"wke"，所以其长度为3。
请注意，你的答案必须是⼦串的长度，"pwke"是⼀个⼦序列，不是⼦串。
⽰例 4:
输⼊: s =""
输出:0
提⽰：
0 <= s.length <= 5 * 104
s 由英⽂字母、数字、符号和空格组成
解题思路： ⼀开始想到循环遍历然后通过indexOf来判断是否有重复的数组，有之后将之前的放⼊⼀个新的数组⾥⾯，然后继续遍历判断重复如此直⾄遍历完所有字符，再判断最长的⼀个。
代码实现：
var lengthOfLongestSubstring=function(s){
let arr =[], max =0
for(let i =0; i < s.length; i++){
let index = arr.indexOf(s[i])
if(index !==-1){
arr.splice(0, index+1);
}
arr.push(s.charAt(i))
max = Math.max(arr.length, max)
}
return maxindexof的用法javascript
};
其他到的⽅法：
维护下标
解题思路： 使⽤下标来维护滑动窗⼝
代码实现：
var lengthOfLongestSubstring=function(s){
let index =0, max =0
for(let i =0, j =0; j < s.length; j++){
index = s.substring(i, j).indexOf(s[j])
if(index !==-1){
i = i + index +1
}
max = Math.max(max, j - i +1)
}
return max
};
2
时间复杂度：O(n)
空间复杂度：O(n)
优化的Map
解题思路：
使⽤ map 来存储当前已经遍历过的字符，key 为字符，value 为下标
使⽤ i 来标记⽆重复⼦串开始下标，j 为当前遍历字符下标
遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新⽆重复⼦串开始下标 i 为相同字符的下⼀位置，此时从 i 到 j 为最新的⽆重复⼦串，更新 max ，将当前字符与下标放⼊ map 中
最后，返回 max 即可
代码实现：
var lengthOfLongestSubstring=function(s){
let map =new Map(), max =0
for(let i =0, j =0; j < s.length; j++){
if(map.has(s[j])){
i = Math.(s[j])+1, i)
}
max = Math.max(max, j - i +1)
map.set(s[j], j)
}
return max
};
时间复杂度：O(n)
空间复杂度：O(n)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。