3-无重复字符的最长子串
标签：哈希表 字符串 滑动窗口
题目信息
题目地址： 无重复字符的最长子串
题目内容：
javascript
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
题解
解法一
思路：
通过双重
for循环来解决，创建一个数组存放不重复的字符串长度第一层
for循环来获取当前遍历的字符的索引，然后从原字符串中截取当前索引到原字符串末尾的字符串第二层
for遍历第一层截取到的字符串，并设置一个Set来存放不重复的字串长度，如果Set中含有当前遍历到字符串，就直接返回Set的size，否则就将当前字符串添加到Set中最后返回存放不重复的字符串长度中最大的数字即可
代码实现：
javascript
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length <= 1) return s.length
const allStrLength = []
const next = str => {
const set = new Set()
for(let i = 0; i < str.length; i++) {
const curStr = str[i]
if(set.has(curStr)) {
return set.size;
}
set.add(curStr)
}
return set.size
}
for(let i = 0; i < s.length; i++) {
allStrLength.push(next(s.slice(i)))
}
return Math.max(...allStrLength)
};
解法二
思路：
设置一个数组
res来存放遍历过程中的不重复字符串，设置最大不重复长度max，使用for循环遍历字符串遍历过程中，设置当前遍历字符串为
curStr，判断curStr是否在res中，如果在，就从
res中截取从curStr的下一位到res结尾的数组，然后赋值给res然后将
curStr放到数组末尾，然后更新max的值，取max和res.length中最大的最后返回
max即可
代码实现：
javascript
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length <= 1) return s.length
let res = []
let max = 0
for(let i = 0; i < s.length; i++) {
const curStr = s[i]
const curStrIdx = res.indexOf(curStr)
if(!!~curStrIdx) {
res = res.slice(curStrIdx + 1)
}
res.push(curStr)
max = Math.max(max, res.length)
}
return max
};
还可以使用
队列思想
代码如下：
javascript
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length <= 1) return s.length
const res = []
let max = 0
for(let i = 0; i < s.length; i++) {
const curStr = s[i]
while(res.includes(curStr)) {
res.shift()
}
res.push(curStr)
max = Math.max(max, res.length)
}
return max
};