每天一道算法题（八）——找出字符串中无重复字符的最长子串

---

1、问题

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

2、示例

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

3、解决方法

（1）方法1——双指针

let s = "abcabcbb";
let lengthOfLongestSubstring = function(s) {
    // 1: 如果字符串的长度小于等于1，返回当前字符串的长度（0/1）
    if(s.length <= 1) return s.length
    // 2-1: 定义左右指针，最大值
    // 和之前双指针不同的在于，当前题目需要依此对比，也就是n开始，和n+1...开始对比
    // 2-2: 定义一个切割字符串后的变量
    let temp;
    let max = 0, left = 0, right = 1; 
    // 3: 左指针固定，右指针小于字符串长度继续遍历
    while(right < s.length){
        // 4: 获取根据左右指针切割的字符串
        temp = s.slice(left, right);
        // 5-0: 判断切割后的字符串是否存在 当前右指针下标的字符串
        // charAt 判断字符串中是否有给定索引（right）的字符串
        if(temp.indexOf(s.charAt(right)) > -1){
            // 5-1: 如果切割后的字符串中有当前右指针索引的下标值，左指针自增并结束循环（需求是返回不重复的字符串）
            left++
            continue;
        } else {
            // 5-2： 如果切割的字符串没有右指针，右指针自增（需求：最长的不重复数据）
            right++
        }
        // 6: 如果右指针 - 左指针 大于 返回最大长度，就把左右指针相减的值给max
        if(right - left > max) {
            max = right - left;
        }
    }
    // 7:输出最大不重复长度
    console.log('最大连续子串长度', max);
};
lengthOfLongestSubstring(s);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

总结

难度： 中等
区别：之前的双指针是从左右两端开始的，当前是由0，1开始的，找到规律。
其他：当你了解上面代码后，你可以看看每天一道算法题（九）——寻找字符串中所有字母异位词的子串这题，和当前这题的思路一样。