无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

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

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解法一：维护数组

解题思路：使用一个数组来维护滑动窗口
遍历字符串，判断字符是否在滑动窗口数组里

• 不在，则push进数组
• 在，则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符push进数组
• 然后将max更新为当前最长子串的长度

遍历完，返回max即可
画图帮助理解一下

代码实现

var lengthOfLongestSubstring = function (s) {
    let arr = [];
    let max = 0;
    for (let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i]);
        //出现重复的字母把数组中这个字母及之前的字符全部删掉
        if (index !== -1) {
            arr.splice(0, index + 1);
        }
        arr.push(s.charAt(i));
        // 取出每次max的最大值
        max = Math.max(arr.length, max);
    }
    return max;
};
console.log(lengthOfLongestSubstring("abcabcbb")); //3

时间复杂度：O(n^2),其中arr.indexOf()时间复杂度为O(n),arr.splice(0, index + 1)的时间复杂度也为O(n)。
空间复杂度：O(n)

解法二：维护下标

解题思路：使用下标来维护滑动窗口
代码实现：

var lengthOfLongestSubstring = function (s) {
    let index = 0;
    let max = 0;
    for (let i = 0, j = 0; j < s.length; j++) {
        index = s.substring(i, j).indexOf(s[j]);
        //如果截取的子串中含有字符，则索引从下一个字符的位置开始
        if (index !== -1) {
            i = i + index + 1;
        }
        // 取出每次max的最大值
        max = Math.max(max, j - i + 1);
    }
    return max;
};
console.log(lengthOfLongestSubstring("abcabcbb")); //3

时间复杂度：O(n^2)
空间复杂度：O(n)

解法三：优化Map

解题思路：
使用map来存储当前已经遍历过的字符，key为字符，value为下标。
使用i来标记无重复子串开始的下标，j为当前遍历字符的下标，遍历字符串，判断当前字符是否已经在map中存在，存在则更新无重复子串开始下标i为相同字符的下一个位置，此时从i到j为最新的无重复子串，更新max，将当前字符与下标放入map中。
最后，返回max即可
代码实现：

var lengthOfLongestSubstring = function (s) {
    let map = new Map();
    let max = 0;
    for (let i = 0, j = 0; j < s.length; j++) {
        //如果map对象中含有字符，则索引从相同字符的下一个字符位置开始
        if (map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i);
        }
        // 取出每次max的最大值
        max = Math.max(max, j - i + 1);
        map.set(s[j], j);
    }
    return max;
};
console.log(lengthOfLongestSubstring("abcabcbb")); //3

时间复杂度：O(n)
空间复杂度：O(n)