title

给定一个字符串, 找出不含有重复字符的最长子串的长度。

示例:

给定 "abcabcbb", 没有重复字符的最长子串是 "abc", 那么长度就是 3
给定 "bbbbb", 最长的子串就是 "b", 长度是 1
给定 "pwwkew", 最长子串是 "wke", 长度是 3。请注意答案必须是一个子串, "pwke" 是子序列而不是子串。

题解

方法名: 滑动窗口是字符串/数组中常用概念

解法一: 判断字符串 s[i, j) 中是否有 s.charAt(j + 1), 如果有, 给左区间加上相应的值, 执行时间大致为 98ms 左右。

具体步骤如下:

  1. 取滑动列表 [left, right];
  2. 若列表 [left, right] 中的取值之和小于 s, 则列表的有边界 right 往右扩张。
  3. 若列表 [left, right] 中的取值之和大于 s, 则列表的左边界 left 往右扩张。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (s.length < 1) {
return 0
}
let i = 0, j = 1, longest = 1
while (j < s.length) {
if (s.slice(i, j).indexOf(s.charAt(j)) > -1) {
i += s.slice(i, j).indexOf(s.charAt(j)) + 1
} else {
longest = Math.max(j - i + 1, longest)
}
j++
}
return longest
}

思考: 针对 判断字符串 s[i, j) 中是否有 s.charAt(j + 1) 这一句, 是否能使用 O(n) 时间复杂度的算法代替 indexOf 呢? 使用 cacheObj 来缓存值, 测试执行时间大致为 170ms 左右。

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0, right = 0 // [left, right] 区域
let result = 0 // 假定结果的初始值为 0
const cacheObj = {}
while (left < s.length) {
if (right < s.length && !cacheObj[s[right]]) {
cacheObj[s[right]] = 1
result = Math.max(result, right - left + 1)
right++
} else {
cacheObj[s[left]] = null
left++
}
}
if (result === 0) {
return 0
}
return result
}

Sister Title

76(todo)、209、438