【LeetCode 力扣】3.无重复字符的最长子串 Java实现 滑动窗口

题目链接：3.无重复字符的最长子串

1 原题描述：

2 解题思路

初看此题，其实并不难理解，我们一共有两个指针，一个时我们子串的头 start ，一个是我们子串的尾 end。我们的尾 end 依次加一，然后判断一下start 到 end - 1 之间有没有和 end 重复的字母。若存在下标为 i 的字母和 end 重复，那么我们需要将我们的头 start 变到当前重复 i 的下一个，也就是 $start=i+1$ ,这样我们的两个指针之间的范围就会不断变化，并且满足题目所说的是一个 不重复 的子串。而这两个指针之间的内容就如同窗口一样，两个指针的变化就是滑动，这就是我们常见的滑动窗口。而我们只需要每次都计算一下当前窗口的长度,然后和之前的最大值相比，保存一个更大的值即 $max=Math.max(max,end-start+1);$

可能还有小伙伴，不太理解，为什么这样滑动能确保我们的窗口能找到长度最长的子串呢？不妨我们看一下下面的几个例子吧。

• $(abcd)ade$ 接下来我们又将获取一个a，而这个a存在重复值，那么我们的 start 将移动到重复值的下一个，也就是 $a(bcda)de$
• $(abcd)bde$ 接下来我们又将获取一个b，而这个b存在重复值，那么我们的 start 将移动到重复值的下一个，也就是 $ab(cdb)de$

观察上面两个例子，我们简单的来说，若想包含第一个重复值，那么 end 就无法向第二个重复值后移动。若想包含第二个重复值，那么 start 必须在第一个重复值后面。

相信大家也就理解了什么是滑动窗口，以及如何求出最长的子串了，那么我们来看看代码是怎么实现的呢？

代码实现1：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        for(int start = 0, end = 0; end < s.length(); end++){
            char ch = s.charAt(end);
            for(int i = start; i < end; i++){
                if(ch == s.charAt(i)){
                    start = i + 1;
                    continue;
                }
            }
            max = Math.max(max, end - start + 1);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

虽然说，我们代码写出来了，可我们可以发现，我们的时间只击败了 19.9% 的人，说明我们还有很大的改进空间。

可以算出我们上面的代码时间复杂度为 $O(n^2)$，那我们怎么优化呢？观察后可发现，我们找 start 到 end - 1 之间有没有和 end 重复的字母这部分代码的时间复杂度为 $O(n)$ ,那我们对这里能优化吗？对了，我们可以使用哈希表来存储我们窗口之间的字母，并且我们需要知道该字母的下标，因此我们要采用 HashMap ， key 用来存储字母， value 用来存储字符位置 +1，加 1 表示从字符位置后一个才开始不重复，这样start 更新就会变得更方便。同时由于 HashMap 的特性是不会存储两个一样的 key，那当窗口滑动时，我们存储新的重复字母就相当于只是修改了原 key 的 value 值。那么我们就可以使用 HashMap 中的 map.containsKey(s.charAt(end)) 来判断我们是否存在重复数字了，而大家也知道 containsKey 的时间复杂度为 $O(1)$，用此替换了我们原本的方法后，我们时间复杂度就优化为 $O(n)$ 了！

那么很轻松的，我们优化后的代码也就出来了！

代码优化：

class Solution {
   public int lengthOfLongestSubstring(String s) {
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(int start = 0, end = 0; end < s.length(); end++){
            if(map.containsKey(s.charAt(end))){
                start = Math.max(map.get(s.charAt(end)), start);
            }
            max = Math.max(max, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14