HOT100——无重复字符的最长子串(JS实现)

题目描述

HOT100——无重复字符的最长子串(JS实现)

解题思路

  • 本题采用双指针 + 哈希表的方式解决问题。
  • 最大值是通过不断更新出来的。
  • 右指针移动到字符串的最后一个元素循环结束。
  • 循环体中首先判断右指针指向的元素是否出现在哈希表中,如果出现了,对应的值+1,反之赋值为1.
  • 哈希表存在的意义就是为了辅助我们的左指针的移动,当右指针的元素出现的次数大于2,此时说明重复了,我们要不断移动左指针,直到右指针重复的这个元素不重复为止,移动左指针之前还要将左指针指向的这个元素的哈希值-1,防止后面出现了同样的元素
  • 最后右指针右移,然后不断比较res和right - left的较大值赋给res。

解题代码

var lengthOfLongestSubstring = function(s) {
    // 本题采用滑动窗口 + 双指针的方法
    // 定义左指针
    let left = 0;
    // 定义右指针
    let right = 0;
    // 定义最大值
    let res = 0;
    // 定义滑动窗口(哈希表)
    let window = new Map();
    // 循环结束条件是 右指针走到了最右边
    while (right < s.length) {
        // 判断右指针指向的元素,是否在哈希表中,在则+1,不在则添加进去
        if (window.has(s[right])) {
            window.set(s[right],window.get(s[right]) + 1);
        } else {
            window.set(s[right],1);
        }
        // 判断右指针指向的元素,是否出现了重复
        while (window.get(s[right]) > 1) {
            // 当右指针指向的元素出现了两次,说明重复了,左指针指向的元素在哈希表中的值-1,然后左指针右移
            // 之所以 -1 之后再右移,根本原因在于防止左边的元素重复出现
            window.set(s[left],window.get(s[left]) -1);
            left++;
        }
        // 指针右移,不断更新最大值
        right++;
        res = Math.max(res,right - left);
    }
    return res;
};
复制代码

参考链接

剑指Offer——最长不含重复字符的子字符串(JS实现)

总结(本题给我们的启示思路)

  • 学会通过不断更新的方式获取最大值。
  • 学会通过哈希表 + 双指针的方式来解决问题。


上一篇:剑指Offer——左旋转字符串(JS实现)


下一篇:剑指Offer——把字符串转换成整数(JS实现)