本文是《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;
}
这里要注意的是:hashmap中任意一个value,表示的是某个元素在整个数组中的位置,而不是在窗口中的位置,因为程序中不会对hashmap做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毫秒,比之前好了不少,如下图:
然而,这个成绩依然很平庸,因为它还有可优化之处,接下来再次优化;
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;
}
至此,LeetCode第三题的解题思路、编码实现、优化实战就全部完成了,希望能给读者您在解题过程中带来一些参考,刷题之路,大家一起努力!