【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
};
成绩:

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论