无重复字符的最长子串

中等

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

题解

以字符串'abcabcbb'为例，从第一个字符开始循环遍历，找出不包含重复字符的最长子串
     以   (a)bcabcbb     开始的最长字符串为  (abc)abcbb     3
     以   a(b)cabcbb     开始的最长字符串为  a(bca)bcbb     3
     以   ab(c)abcbb     开始的最长字符串为  ab(cab)cbb     3
     以   abc(a)bcbb     开始的最长字符串为  abc(abc)bb     3
     以   abca(b)cbb     开始的最长字符串为  abca(bc)bb     2
     以   abcab(c)bb     开始的最长字符串为  abcab(cb)b     2
     以   abcabc(b)b     开始的最长字符串为  abcabc(b)b     1
     以   abcabcb(b)     开始的最长字符串为  abcabcb(b)     1
最终的结果是3

可以发现一个规律，开始字符串和结束字符串都是递增的
这样就可以使用滑动窗口来解决这个问题了
滑动窗口需要两个指针，左指针用来指向开始的字符，右指针用来指向结束的字符
由于需要循环，左指针借助每次循环的那个i

代码如下

使用了一个数组来存储没重复的字符
shift 方法来实现左指针前进
includes 方法判断是否为重复子串
也可以使用 Set 来实现

JavaScript

var lengthOfLongestSubstring = function (s) {
  // 右指针
  let rk = -1;
  // 用来保存字符串
  const arr = [];
  // 用来保存最长子串的长度
  let ans = 0;
  // 字符串长度
  let n = s.length;

  for (let i = 0; i < n; i++) {
    // 左指针前进
    if (i !== 0) arr.shift();

    while (!arr.includes(s[rk + 1]) && rk + 1 < n) {
      // 如果没有重复字符则把当前字符放入数组中
      arr.push(s[rk + 1]);
      // 右指针前进
      rk++;
    }
    // 取较大值
    ans = Math.max(arr.length, ans);
  }
  return ans;
};

例如字符串 abcabcbb
每次判断当下一个字符不重复时，右指针则向前移动

第一次循环
     一开始的下一个字符为a，右指针前进 [a]bcabcbb
     下一个字符b，右指针前进 [ab]cabcbb 
     下一个字符c，右指针前进 [abc]abcbb 
     下一个字符a，重复，长度为3，结束

第二次循环
     左指针前进 a[bc]abcbb
     下一个字符a，右指针前进 a[bca]bcbb
     下一个字符b，重复，长度为3，结束

第三次循环
     左指针前进 ab[ca]bcbb
     下一个字符b，右指针前进 ab[cab]cbb
     下一个字符c，重复，长度为3，结束

第四次循环
     左指针前进 abc[ab]cbb
     下一个字符c，右指针前进 abc[abc]bb
     下一个字符b，重复，长度为3，结束

第五次循环
     左指针前进 abca[bc]bb
     下一个字符b，重复，长度为2，结束

第六次循环
     左指针前进 abcab[c]bb
     下一个字符b，右指针前进 abcab[cb]b
     下一个字符b，重复，长度为2，结束

第七次循环
     左指针前进 abcabc[b]b
     下一个字符b，重复，长度为1，结束

第八次循环
     左指针前进 abcabcb[]b
     下一个字符b，右指针前进 acbabcb[b]
     遍历完成，长度为1，循环结束

无重复字符的最长子串 ​

题解 ​

无重复字符的最长子串

题解