每日一道 LeetCode (46)：无重复字符的最长子串
共 1226字，需浏览 3分钟
·
2020-09-15 09:19
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：无重复字符的最长子串
题目来源：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题方案一：暴力方案
看到这道题的第一个反应是这题我做过！！
然后我往前一顿翻，结果嘛。。。
emmmmmmmmmmm。。。
没找着。
既然找不着那就开始想，这题是要求一个最长无重复的子串，重点总共就两点：
无重复 子串
最后是要求一个最长的长度，这其实就是把所有的不重复子串的长度穷举出来，然后取最大就完事儿。
经过上面的分析，我们成功的把这道题转化成了一个求不重复子串的问题。
思路是滑动窗口，首先子串肯定是有长度的，即使只有 1 也是有长度的。
这时，我们指定两个指针，一个左一个右，左右指针之间的内容实际上就是我们的子串，长度就是我们的子串长度。
两个指针位于初始位置时，开始移动右指针，然后每次移动以后判断指向的元素是否和之前已有的元素有重复，如果没有重复就一直向右移，直到有重复的为止，这就是我们的第一个子串，然后记录这个子串的长度。
接下来左指针右移一位，然后再重复上面的过程，一直到左指针移动完整个字符串，这时我们就遍历完成了所有的不重复的子串。
判断子串是否用重复可以通过数据结构来判断，通常常用的有哈希表。
接下来就是代码实现：
public int lengthOfLongestSubstring(String s) {
Set setChars = new HashSet<>();
int length = s.length();
// 定义右指针
int right = -1;
// 定义返回结果
int result = 0;
for (int i = 0; i < length; ++i) {
if (i != 0) {
// 左指针右移一次，删掉前一个字符
setChars.remove(s.charAt(i - 1));
}
while (right + 1 < length && !setChars.contains(s.charAt(right + 1))) {
// 移动右指针，像 set 中添加字符
setChars.add(s.charAt(right + 1));
++right;
}
result = Math.max(result, right - i + 1);
}
return result;
}
解题方案二：优化后
上面这个方案有个缺陷，就是每次左指针只是单纯的 + 1 ，实际上左指针可以直接移动到右指针 + 1 的位置，因为当前的子串已经有重复了，直接跳过就好了。
public int lengthOfLongestSubstring_1(String s) {
int length = s.length(), result = 0;
Map map = new HashMap<>();
for (int left = 0, right = 0; right < length; right++) {
// 如果含有右指针指向的元素，则移动左指针
if (map.containsKey(s.charAt(right))) {
left = Math.max(map.get(s.charAt(right)), left);
}
result = Math.max(result, right - left + 1);
map.put(s.charAt(right), right + 1);
}
return result;
}
解题方案三：极致优化
上面的方案还有没有优化空间，当然有，我们对循环次数已经没办法优化了，那么还能优化的就剩下了判断当前字符是否存在。
比哈希表寻址还要快的可能有什么？当然是直接操作数组咯~~~
首先可以定义一个 128 位的数组，然后我们通过数组进行判断当前字符是否存在：
public int lengthOfLongestSubstring_2(String s) {
int n = s.length();
int result = 0;
int[] charIndex = new int[128];
for (int left = 0, right = 0; right < n; right++) {
char c = s.charAt(right);
left = Math.max(charIndex[c], left);
result = Math.max(result, right - left + 1);
charIndex[c] = right + 1;
}
return result;
}
