给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 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};
成绩: