xszi
commented
3 years ago 方法1：维护数组
const longestSubstring = (str) => {
if (!str || !str.length === 0) return 0
let arr = str.split('')
let temp = [], maxLength = 0
for (let i = 0; i < arr.length; i++) {
const index = temp.indexOf(arr[i]);
if (index !== -1) {
if (temp.length > maxLength) {
maxLength = temp.length
}
temp = temp.slice(index + 1, temp.length)
}
temp.push(arr[i])
}
return maxLength
}时间复杂度： O(n^2) 空间复杂度： O(n)
方法2：维护下标
const longestSubstring = (str) => {
if (!str || !str.length === 0) return 0
let index = 0, maxLength = 0
for (let i = 0, j = 0; j < str.length; j++) {
index = str.substring(i, j).indexOf(str[j]);
if (index !== -1) {
const length = j - i
if (length > maxLength) {
maxLength = length
}
i = i + index + 1
}
}
return maxLength
}时间复杂度： O(n^2) 空间复杂度： O(n)
方法3：Map
解题思路：
使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标
使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标
遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中
最后，返回 max 即可
const longestSubstring = (str) => {
if (!str || !str.length === 0) return 0
let map = new Map(), maxLength = 0
for(let i = 0, j = 0; j < str.length; j++) {
if (map.has(str[j])) {
// i = map.get(str[j]) + 1
i = Math.max(map.get(str[j]) + 1, i) // 比较的意义，为什么要取最大值？
}
maxLength = Math.max(maxLength, j - i + 1)
map.set(str[j], j)
}
return maxLength
}时间复杂度： O(n) 空间复杂度： O(n)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
示例 2:
示例 3:
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
leetcode