目录

1 题目

2 输入输出

3  解法—滑动窗口

4 代码

1 题目

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

2 输入输出

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

3  解法—滑动窗口

暴力解法时间复杂度较高，会达到 O(n^2)，故而采取滑动窗口的方法降低时间复杂度

定义一个对象或者Map数据结构存储 (key, value)，其中 key 值为字符，value 值为字符位置。

定义不重复子串的开始位置为 start，结束位置为 end

随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符（也就是说，如果前面出现一样的，那么可以认为将上一次出现该字符的地方以及之前序列删除）

无论是否更新 start，都会更新对象或者 map 数据结构和结果maxLen。

时间复杂度：O(n)

4 代码

/**
 * @param {string} str
 * @return {number}
 * 求无重复字符的最长子串
 * 方法：使用滑动窗口+双指针
 */
var lengthOfLongestSubstring = function(str) {
    if(str.length <= 1){
        return str.length;//长度为0和1时
    }
    let map = new Map();
    let maxLen = 0;//最长子串的长度，初始为0
    for(let end = 0, start = 0; end < str.length; end++){ //end遍历整个数组
        if(map.has(str[end])){ //map存在该字符
          start = Math.max(start, map.get(str[end]) + 1);//从上一个与之相同字符的下一个字符开始
        }
        /*else {//不存在 不需要更新start的位置，可省略

        }*/
        //如果str[end]在map中存在，则更新键为str[i]的对应的值为新出现的位置；如果不存在，则添加键值对(值为对应下标)
        //map存不存在该字符都应该设置/更新键值，以及求取maxLen
        map.set(str[end], end);
        maxLen = Math.max(maxLen, end - start + 1);
    }
    return  maxLen;
};
console.log(lengthOfLongestSubstring("abcabcbb"));

参考：力扣

百里于2020年5月23日

如果有错，请您指出！如有侵权，请联系我删除！