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

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

欢迎访问我的GitHub

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

原有代码

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

public int lengthOfLongestSubstring(String s) { //窗口的起始位置,窗口的结束为止,最长记录 int left = 0, right = 0, max = 0; //表示窗口内有哪些值 Set 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; }

第一次优化

这里要注意的是：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 map = new HashMap<>(); while (right=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; }

第二次优化

如上所示，长度为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-1){ int pos = array[offset]; if(pos>=left){ left = pos + 1; } } array[offset] = right++; if((right-left)>max){ max = right-left; } } return max; }

欢迎关注51CTO博客：程序员欣宸

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。