xszi
commented
3 years ago 方法一： 队列思想维护数组
const maxLength = (s) => {
let queue = []
let length = 0
for (let i = 0; i < s.length; i++) {
if (queue.indexOf(s[i]) < 0) {
queue.push(s[i])
} else {
length = Math.max(queue.length, length)
// 将队列元素删除，直到与当前元素相等，且将当前元素入队
while(queue.shift() !== s[i]) {
queue.push(s[i])
}
}
}
return length
}
时间复杂度：O(n^2) 空间复杂度：O(n)
方法二： 数组API维护数组
const maxLength = (s) => {
let length = 0
let arr = []
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[i])
length = Math.max(arr.length, length)
}
return length
}时间复杂度：O(n^2) 空间复杂度：O(n)
方法三： 维护下标
const maxLength = (s) => {
let index = 0, length = 0
for (let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s.charAt(j))
if (index !== -1) {
i = i + index + 1
}
length = Math.max(length, j - i + 1)
}
return length
}时间复杂度：O(n^2) 空间复杂度：O(n)
方法四：使用Map 维护下标
const maxLength = (s) => {
let map = new Map(), length = 0
for (let i = 0, j = 0; j < s.length; j++) {
if (map.has(s[j])) {
// i = Math.max(map.get(s[j]) + 1, i)
i = map.get(s[j]) + 1
}
length = Math.max(length, j - i + 1)
map.set(s[j], j)
}
return length
}时间复杂度：O(n) 空间复杂度：O(n)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
示例 2:
示例 3:
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
leetcode