乐趣区

关于前端:LeetCode-3-无重复字符的最长子串

Hi,大家好,我是小庄。

明天打卡的算法题是 —— 力扣 3. 无反复字符的最长子串

该题是校招 + 社招中,考查频率排名第二的算法题,考查频率排名第一的是反转链表,具体解法请看公众号中的上一篇文章。

该题将采纳「哈希表 + 滑动窗口」实现,话不多说,一起来学习吧~

一、Leetcode 题目

1、题目地址

点击查看 Leetcode 题目

2、具体题目


二、实现代码

1、思路:哈希表 + 滑动窗口

(1)具体代码

/**
 * @param {string} s
 * @return {number}
 */
//  哈希表 + 滑动窗口
// 工夫复杂度: O(n),n 为字符串 s 的长度
// 空间复杂度: O(n), n 为 map 的长度
var lengthOfLongestSubstring = function(s) {let map = new Map();
    let start = 0;
    let end = 0;
    let max = 0;
    while(true) {if(end >= s.length) {break;}
        let temp = map.get(s[end]);
        //map 中还没存在
        if(temp === undefined || temp < start) {max = Math.max(max, end - start + 1);
        }else {//map 中曾经存在了
            start = temp + 1;
        }
        map.set(s[end], end);
        end++;
    }
    return max;
};

(2)运行后果

三、解说视频

点击查看 B 站解说视频

四、补充局部

** 关注公众号:【深漂程序员小庄】:
内含丰盛的学习资源和面试教训(不限前端、java),还有学习交换群可加,并且还有各大厂大佬可一起交流学习,一起提高~增加小庄微信,回复【加群】,可退出互联网技术交换群。**

本文由 mdnice 多平台公布

退出移动版