LeetCode刷题日志#3:无重复字符的最长子串 - 滑动窗口法

题目:传送门
类别:字符串
难度:中等
相关算法:滑动窗口法

思路

准备一个空数组做寄存数组。从左往右开始读字符串,准备一个一个字符往寄存数组里添加。

加之前要先判断下,如果寄存数组没有,那直接加就是;如果已经有了,那么从寄存数组里该字符位置的下一个位置截断寄存数组,构成新的寄存数组。

当然要记下原来寄存数组的长度,比较下,新的更长就更新。记当度就够了,题目只要长度,不要求字串是什么。当然要的也简单,记两个下标即可。

代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let largestLen = 0;
  let uniqueArr = [];
  
  for (let i = 0, len = s.length; i < len; i += 1) {
    const currentChar = s[i];
    
    const lastIndex = uniqueArr.indexOf(currentChar);
    if (lastIndex > -1) {
      uniqueArr = uniqueArr.slice(lastIndex + 1);
    }
    uniqueArr.push(currentChar);
    
    const uniqueArrLen = uniqueArr.length;
    if (uniqueArrLen > largestLen) {
      largestLen = uniqueArrLen; 
    } else {
      // 优化:提前结束
      if (largestLen >= uniqueArrLen + len - i) {
        return largestLen;
      }
    }
  }
  
  return largestLen;
};

思考

发现,如果 uniqueArr 改为字符串还会更快,内存消耗更小点。

还有,原来这个叫滑动窗口法?

评论

暂无评论