给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
题目详解
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
可行-穷举
那么一开始肯定是最Lowwwwwww的了
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let result = []
let maxLength = 0
for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
result.push(s.slice(i, j))
}
}
result.forEach(array => {
let temp
for (let i = 0; i < array.length; i++) {
temp = array.slice(0, i).concat(array.slice(i + 1))
if (temp.indexOf(array[i]) > -1) {
return
}
}
if (array.length > maxLength) {
maxLength = array.length
}
})
return maxLength
};
勉强能用-键值对
- 先外层遍历一次
- 从外层遍历的起点开始往后新增字符,校验并记录满足条件的最大长度
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let map
let maxLength = 0
for (let i = 0; i < s.length; i++) {
map = Object.create(null)
let length = 1
map[s[i]] = s[i]
for (let j = i + 1; j < s.length; j++) {
if (map[s[j]] !== undefined) {
break
} else {
map[s[j]] = s[j]
length++
}
}
if (length > maxLength) {maxLength = length}
}
return maxLength
};
勉强能见人优化-滑块
- 从左至右滑动滑块,若新进字符(右)不重复,则不移除末尾字符(左)
若新进字符与已存在字符重复,则移除左起点至被重复字符的字符字串,
- 比如当前滑块为“abcde”,新进字符为c,则移除“abc”
- 滑块右移,并比较当前长度与最大长度
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let _window = []
let maxLength = 0
let index = 0
let temp
let tempIndex
while (index < s.length) {
temp = s[index]
tempIndex = _window.indexOf(temp)
if (tempIndex === -1) {
_window.push(temp)
if(_window.length > maxLength) { maxLength = _window.length}
} else {
_window.splice(0, tempIndex + 1)
_window.push(temp)
}
index++
}
return maxLength
};
再优化
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
if(!s) return 0;
if(s.length == 1) return 1;
let index, temp, len
let arr = new Array(256) //在JavaScript中一个函数最多拥有255个参数
arr.fill(-1)
let startIndex = 0
let maxLength = 0
for (let i = 0; i < s.length; i++) {
temp = s[i].charCodeAt()
index = arr[temp]
if (index !== -1 && index >= startIndex) {
len = i - startIndex
if (len > maxLength) { maxLength = len }
startIndex = index + 1
}
arr[temp] = i
}
if (maxLength < (s.length - startIndex)) {maxLength = s.length - startIndex}
return maxLength
};
2 comments
宝贝 你太强了
你在说什么骚话