Leetcode刷题(第3题)——无重复字符的最长子串

x33g5p2x  于2022-02-21 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(161)

一、题目描述
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
二、示例

示例一:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例二:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

三、思路
可以使用双指针left和right指针,右指针遍历当前字符串的每一个下标,并且使用一个哈希表来保存当前字符串的值以及其下标。如果当前的值已经在map中存在,并且重复值的下标大于或者等于left的值,此时需要移动左指针,将其移动到重复的值的下一位。然后不断的向map中放入值(如果重复则会被覆盖),以及不断的计算max的值。
四、代码

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let max = 0;
    let map = new Map()
    let length = s.length
    for(let right = 0; right < length; right++) {
        if(map.has(s[right]) && map.get(s[right]) >= left) {
            left = map.get(s[right]) + 1
        }
        map.set(s[right], right)
        max = Math.max(max, right - left + 1)
    }
    return max
};

五、分析
时间复杂度为O(n),空间复杂度为O(n).

相关文章

微信公众号

最新文章

更多