【图解】三种解法不断优化带你手撕 LeetCode第三号题：无重复字符的最长子串
【图解】三种解法不断优化带你手撕 LeetCode第三号题：无重复字符的最长子串
来源于公众号：苦逼的码农
作者：stul
刷题，AC 不是最终目的，而应该力求最优解，并且总结归纳每个解法的精髓
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例1：
输入: "abcabcbb"输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2：
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路与解法
思路1：暴力法，实际解题中不会使用暴力法，这并不代表我们可以忽略它。
索引从字符串的第一位开始，将后面的字符依次加入到 set 里面。如果 set 里面已经有了该字符，此次循环结束，内循环结束后记录 size。字符串的每一位都用这种方法去计算，得到的最大的 size 即是答案。
代码如下（不是Java的也看得懂，我进行了关键语法的注释，下同）
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
for(int i = 0; i < s.length(); i++){
// 创建一个存放字符的集合
HashSet<Character> set = new HashSet<>();
for(int j = i; j < s.length(); j++) {
// 判断集合是否存在第 j 个字符
if(set.contains(s.charAt(j)))
break;
set.add(s.charAt(j));
}
maxLen = Math.max(maxLen,set.size());
}
return maxLen;
}
（为方便阅读，给出截图）
时间复杂度：O()
空间复杂度：O(m) ，m 为无重复字符的最长子串的长度。
由 思路1 的图可知，i 每次都从下一位开始，其实做了很多无效的计算。思路2将其优化。
思路2：我们设置两根指针（i 和 j ）与一个集合set。两个指针之间是一个范围，我们要维护这个范围内不能出现重复的字符。而这个 set 就是是用来判断范围内是否有重复的字符。具体做法如下：i 和 j 开始的时候都指向 字符串首。然后执行下面两个步骤。
- 如果 j 指针所指元素未在 set 里面，我们将其 add 进 set 。继续后移 j 。
- 如果 j 指针所指元素在 set 里面，我们将 i 指针所指元素从 set 中移除，继续后移 i 。i 会一直往后移，直到 j 的元素不在 set 里面。
我们那示例 2 来详细理解一下。
这个过程中，i 与 j 的范围最大的时候，就是我们要求的答案。
HashSet<Character> set = new HashSet<>();
int i = 0, j = 0, maxLen = 0;
while (i < s.length() && j < s.length()){
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j));
j++;
maxLen = Math.max(maxLen,j - i);
}else {
set.remove(s.charAt(i));
i++;
}
}
return maxLen;
代码图片
时间复杂度：O(2n) = O(n) ， i 和 j 两个指针。
空间复杂度：O(m) ，m 为无重复字符的最长子串的长度。
思路2 中，我们在遇到重复的字符时，不断在移动 i 指针。这个地方其实可以优化，让 i 指针直接跳到重复元素的下一个位置。
思路3: 让 i 指针直接跳到重复元素的下一个位置。那我们就需要保存每个元素以及它的位置。一个 Value, 一个 Index 。自然会想到 HashMap 。
我们继续拿示例 2 来演示一下。
这个地方，能看到优化，但是并不明显。测试用例：pabcwwkew，在纸上用思路 2 和思路 3 画一下这个过程，你会发现思路 3 比思路 2 省略了很多步骤。
public static int lengthOfLongestSubString4(String s){
// 创建一个 key-value 为 字符-下标 相映射的哈希表
HashMap<Character,Integer> map = new HashMap<>();
int left = 0, maxLen = 0;
for(int i = 0; i < s.length(); i++){
// 判断是否存在该key
if(map.containsKey(s.charAt(i))){
left = Math.max(map.get(s.charAt(i)) + 1,left);
}
maxLen = Math.max(maxLen, i - left + 1);
map.put(s.charAt(i),i);
}
return maxLen;
}
代码图片
时间复杂度: O(n) ， 最优解。空间复杂度: O(m) ，m 为无重复字符的最长子串的长度。
在上面所提到的 “范围”，就是一个滑动窗口。
其他 leetcode 题目
- 【leetcode】16. 最接近的三数之和
- 【leetcode】15：三数之和
- 【leetcode】14：最长公共前缀
- 【leetcode】13：罗马数字转整数
- 【leetcode】12：整数转罗马数字
- 【leetcode】11. Container With Most Water | 盛最多水的容器
推荐阅读全部文章详细分类与整理（算法+数据结构+计算机基础）
写了很久，这是一份适合普通大众/科班/非科班的『学习路线』有必要说一说即将到来的春招（经历+重要性+如何准备）
普普通通，我的三年大学历经两个月，我的秋招之路结束了！