Longest Substring Without Repeating Characters —— leet code 每天一练

滑动窗口

function lengthOfLongestSubstring(s: string) {
  // const hashMap: { [key: string]: number } = {};
  let max = 0;
  let first = "";
  s.split('').forEach((value: string) => {
    const indxe = first.indexOf(value);
    if (indxe === -1) {
      first += value;
    } else {
      max = first.length > max ? first.length : max;
      first = first.substr(indxe + 1) + value;
    }
  });
  max = first.length > max ? first.length : max;
  return max;
}

运行情况:

Runtime: 88 ms, faster than 95.16% of JavaScript online submissions forLongest Substring Without Repeating Characters.
Memory Usage: 40 MB, less than 66.18% of JavaScript online submissions forLongest Substring Without Repeating Characters.

上面的算法利用了类似于滑动窗口的动作,获取到相同字符的位置,然后得到该子字符串。

复杂度分析:

  • 时间复杂度: O(n + m) or O(n) = O(2n) in the worst case that each other character will be visited twice, ex: str = abcdefg.

  • 空间复杂度:O(min(n, m)), 要么就是目标字符 s 的长度,要么就是子字符串 fist 的长度。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章