[JS][字符串]无重复字符的最长子串

leetcode刷到这道题目，总结起来题目不难，就是官解硬是看不懂，就琢磨了一下。贴一下官解代码：

var lengthOfLongestSubstring = function(s) {
    // 哈希集合，记录每个字符是否出现过
    const occ = new Set();
    const n = s.length;
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指针向右移动一格，移除一个字符
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不断地移动右指针
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本站地址：https://www.nowcoder.com/questionTerminal/2787a88e2a8a4769added6a9be8e4857

思路

暴力遍历是可以解决这个问题的，而且也不会超时。

基础思路

建立一个状态存储当前的不重复字符串str，另一个状态存不重复字符串的最大长度max
设n为0，作为索引的记录，遍历字符串，索引为i，发现重复数字，则n<-n+1，i<-n，max<-str.length>max?，str<-''
直到遍历完成

代码实现:

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    /* TODO:
        1. 记录字符串 str
        2. include ? if include 下一个
     */
     let str = '';/* 存储的字符串 */
     let max_len = 0; /* 存储长度 */
     let c_index = 0; /* 字符串 位置 */
     for (let i = 0; i < s.length; ++i) {
        if (!str.includes(s[i])) {
            str = `${str}${s[i]}`;
        } else {

            str = '';
            i = c_index;
            ++c_index;
        }
        max_len = Math.max(max_len, str.length);
     }
     return max_len;
};

很明显，这样子实现会出现部分无用的循环，可以自行调试一下。需要再优化一下。

优化

思路是基本一致的，我们需要尝试手动做一下这个过程。

0 abcdabcdaabccd

1 abcdabcdaabccd 
  ----
2 abcdabcdaabccd
   ----
3 abcdabcdaabccd
    ----
4 abcdabcdaabccd
     ----
5 abcdabcdaabccd
      ----
6 abcdabcdaabccd
       ----
7 abcdabcdaabccd
           ---
8 abcdabcdaabccd
              --

按照之前的思路，我们中间省略立一大部分的重复过程，而使用代码也能实现这个过程。

存储遍历的不重复的字符串str<-''，最大长度res
遍历字符串s，索引i，index<-?str index in s[i]，max判断并赋值
判断index，若包含，则删掉包含之前的字符并添加现在判断的字符，直到遍历字符串为止

明显只需要遍历一个字符串就行，不需要修改遍历过程中的索引，而且str不用重复置为空再重新开始添加。

这里str使用数组替代：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    /* TODO:
     */
    let res = 0;
    let str_arr = [];
    let index = 0;/* 记录上一个位置 */

    for (let i = 0; i < s.length; ++i) {
        index = str_arr.indexOf(s[i]);
        if (index === -1){/* 不包含 则推入 */
            str_arr.push(s[i]);
        } else {
            /* 包含则释放该数组第一个出现该字符之前 */
            str_arr = str_arr.slice(index+1);/* +1 确保 不要该数字 */
            str_arr.push(s[i]); /* 直接放到后面 */
        }
        res = Math.max(str_arr.length, res);
    }
    return res;
};

官解

自己调试了一遍，官解有重复的过程。

它是一个暴力解不清空的过程，如果遇到重复字符不会跳到下一个，而是删掉第一个字符，继续对比添加。如果有重复的值，比如下面过程

0 aabbaab

1 aabbaab
  -
2 aabbaab

3 aabbaab
   -
4 aabbaab
   --
5 aabbaab
    -
6 aabbaab

7 aabbaab
     -
8 aabbaab
     --
...
...

对比之前的优化

0 aabbaab

1 aabbaab
  -
2 aabbaab
   -
3 aabbaab
   --
4 aabbaab
     -
5 aabbaab
     --
6 aabbaab
       -
7 aabbaab
       --

明显更少循环。

小结

就是有点在意这个，还有七成以上的人，究竟用的是什么方法？

优化方法时间复杂度时O(N)，无论如何都是遍历完字符串，如果再减少循环，可以对比剩余长度和现有长度：

            /* 如果此时 res 比 剩余长度大 则不需要继续遍历了 */
            if (
                (s.length - i /* 剩余的个数 */ + str_arr.length /* 目前拥有的个数 */) <= res
                /* 如果无法达到比现在数字还大的数字，跳出循环 */
            ) {
                break;
            }

这样就可以处理类似于回文的情况了。但有点太极端立。减少了40ms。

AC2

如果遇到类似的问题，应当尝试减少遍历循环。

尽可能保存现有的状态；
尽可能保证不修改索引值（一次循环）；
找到特殊情况（大量出现的）特殊处理；

自行画图有助于最优算法的出现。