LeetCode 第三题 (Longest Substring Without Repeating Characters) 三部曲之三：两次优化

作者：程序员欣宸

2022 年 8 月 04 日
本文字数：3728 字
阅读完需：约 12 分钟

LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三：两次优化

欢迎访问我的 GitHub

这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos

本文是《LeetCode 第三题(Longest Substring Without Repeating Characters)三部曲》的第三篇，之前的两篇文章列出了思路并写出了 Java 代码，虽然在 LeetCode 网站提交通过，但是成绩并不理想，40 多毫秒的速度，与诸多优秀的方案有不小差距，今天就来一起优化代码，提升速度；

三部曲完整链接

原有代码

这里再回顾一下原有代码：

public int lengthOfLongestSubstring(String s) {        //窗口的起始位置,窗口的结束为止,最长记录        int left = 0, right = 0, max = 0;
        //表示窗口内有哪些值        Set<Character> set = new HashSet<>();
        while (right < s.length()) {            //例如"abcdc"，窗口内是"abcd"，此时right等于[4],            //发现窗口内有array[right]的值，就缩减窗口左边，            //缩到窗内没有array[right]的值为止，            //当left一路变大，直到left=3的时候，窗口内已经没有array[right]的值了            if (set.contains(s.charAt(right))) {                //假如窗口内是"abc"，当前是"c"，那么下面的代码只会将"a"删除,left加一，再次循环                //而新一次循环依旧发现"c"还在set中，就再把"b"删除，left再加一...                set.remove(s.charAt(left++));            } else {                //窗口内没有array[right]的时候，就把array[right]的值放入set中，表示当前窗口内有哪些值                set.add(s.charAt(right++));
                if ((right - left) > max) {                    max = right - left;                }            }        }
        return max;    }

复制代码

第一次优化

这次的重点是 HashSet 对象，此对象保存窗口中的所有元素，每加入一个新元素之前都检查 HashSet 中是否存在该元素；
如下图所示，代码中通过 set.add 和 set.remove 方法将 HashSet 中的内容始终与窗口中的内容保持一致：
优化前：判断一个元素是否在窗口中，现在的做法是以 HashSet 中为准，当判定某个元素要从窗口中移除，就调用 HashSet 的 remove 方法从 HashSet 中删除；
上述的代码可以优化，优化后可以不用执行 HashSet 的 remove 方法，具体的逻辑是使用 HashMap 替代 HashSet，HashMap 的 key 是字符串的元素，value 是元素在数组中的位置，举个例子，当 left=1，right=3 时，整体的效果是下图这样的，HashMap 中已经保存了"a"、"b"、"c"三个元素作为 key，而 value 就是它们在数组中的下标：
现在要检查数组中下标为 4 的元素"b"：以"b"为 key 查找 HashMap，如果不存在就表示不在窗口中，如果存在，就用对应的 value=1 去和 left 比较，如果小于 left 就表示不在窗口中，如果大于或者等于 left 就表示在窗口中，如下图所示：

这里要注意的是：hashmap 中任意一个 value，表示的是某个元素在整个数组中的位置，而不是在窗口中的位置，因为程序中不会对 hashmap 做 remove 操作；
接着上面的图分析，"b"元素被发现在窗口中存在后，除了将 left 调整为 2，right 调整为 4，还要调用 HashMap 的 put 方法，将"b"元素的位置从原来的 1 更新为 4；
另外还有个优化点：假设当前窗口中是"abc"，而检查的元素是"b"，之前的代码中，要执行两次循环：先删除"a"，left 加一，再删除"b"，left 再加一，现在用了 HashMap 就能得到"b"的位置，直接将 left 改为"b"的下一个位置即可，不需要执行两次循环了；
以上就是优化思路了，用 HashMap 取代 HashSet，不再执行 remove 方法，对代码的调整并不大，调整后的完整代码如下：

public int lengthOfLongestSubstring(String s) {        int left =0, right =0, max = 0;        Map<Character,Integer> map = new HashMap<>();        while (right<s.length()){          //map中如果不存在就表示不在窗口中            if(map.containsKey(s.charAt(right))){                int pos = map.get(s.charAt(right));                //map中如果存在，再检查value和left，来判断是否在窗口中                if(pos>=left){                  //注意这又是个优化点，假设当前窗口中是"abc"，而检查的元素是"b"，                  //之前的代码中，要执行两次循环：先删除"a"再删除"b"，                  //现在用了HashMap就能得到"b"的位置，直接将left改为"b"的下一个位置即可，不需要执行两次循环了                    left = pos + 1;                }            }            map.put(s.charAt(right), right++);            if((right-left)>max){                max = right-left;            }        }
        return max;    }

复制代码

提交上述代码到 LeetCode，这次的成绩是 27 毫秒，比之前好了不少，如下图：
然而，这个成绩依然很平庸，因为它还有可优化之处，接下来再次优化；

第二次优化

第一次的优化点是消除 remove 方法和 while 循环次数，第二次优化则是针对 HashMap，每次处理新的元素都涉及到 HashMap 的操作，如果您对 HashMap 的内容有所了解，就知道计算 hashcode、创建 EntrySet，调用 equals 方法这些操作会被频繁执行，如果能省去这些操作，那么性能应该会有明显提升，问题是：如何才能去掉 HashMap 而不影响功能呢？
我们先明确 HashMap 在程序中的作用：保存一个元素在数组中的位置，所以优化的方向就是寻找 HashMap 的替代品；
假设一共可能出现二十六种字符：从"a"到"z"，那就简单了，用一个长度为 26 的 int 数组来记录每个字符的位置，array[0]的值就是元素"a"的位置，array[1]的值就是元素"b"的位置，array[2]的值就是元素"c"的位置，如下图所示，图中的数字 97 是"a"的 ASCII 码：
按照上面的设计，array[0]=3 就表示"a"元素在整个数组中最后一次出现的位置是 3，array[1]=1 表示"b"元素在整个数组中最后一次出现的位置是 1，array[2]=2 就表示"c"元素在整个数组中最后一次出现的位置是 2，如下图：
按照以上设计是不是就可以立即编码并提交到 LeetCode 了呢？我当时就是这么做的，很不幸因为测试没有通过而提交失败了，没通过的原因是：字符串中不仅会有"a"到"z"的小写，还有大写字母、空格字符、加减乘除等字符，遇到这些字符时，我们之前设计的长度 26 的数组就不够用了，看来要重新设计数组；
新的数组总长度是 95，这是因为所有英文可见字符一共是 95 个，从空格开始，到"`"结束，如下图的三个红框所示：

如上所示，长度为 95 的数组，可以将所有可见字符都纳入进来，array[0]保存的是空格字符的位置，因此计算字符"a"在 array 数组中的下标就从之前的**'a'-97=0 变成了'a'-32=65**；
另外要注意的是，这个数组中每个元素初始值都是**-1**，表示字符串中没有这个元素(或者说还没有处理到)；
按照上述思路优化后的代码如下所示，可见改动并不大，只是把 HashMap 相关的地方全部改成了上述的数组逻辑：

public int lengthOfLongestSubstring(String s) {        int left =0, right =0, max = 0;
        int[] array = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                -1, -1, -1, -1, -1};
        int offset;        while (right<s.length()){      //offset表示当前处理的元素在array数组中的下标，      //如果当前元素是空格，那么减去32后等于0，array[offset]即array[0],      //这个array[0]的值就是空格字符在字符串中的位置            offset = s.charAt(right) - 32;
            if(array[offset]>-1){                int pos = array[offset];
                if(pos>=left){                    left = pos + 1;                }            }
            array[offset] = right++;
            if((right-left)>max){                max = right-left;            }        }
        return max;    }