【leetcode】3. 无重复字符的最长子串

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

实现思路:

一个简单的滑动块的操作,利用一个队列作为滑块,循环过程中元素不断进入这个队列,作为子串,一旦遇到有重复的元素,就将其本身及左边的元素移出。完成循环后取队列中出现的最大长度即可。

我实现中有一个的小技巧,在剔除重复子串的操作中,我没有将队列进行循环剔除,而是记录重复子串出现的位置,利用 slice 将队列进行一次性切割,提高算法性能。

我的实现:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let queue = []
  let result = 0
  const sLen = s.length
  for (let i = 0; i < sLen; ++i) {
    const item = s[i]
    const index = queue.indexOf(item)
    queue.push(item)
    if (-1 !== index) queue = queue.slice(index + 1)
    else result = Math.max(result, queue.length)
  }
  return result
};

成绩:

clipboard.png

clipboard.png

评论

暂无评论