LeetCode | 3. 无重复字符的最长子串
一、题面
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
二、题解
思路和算法
本题主要采用滑动窗口的思想：
暴力解法每次遇到重复的字符都会从下一个字符开始；
滑动窗口则是从冲突的字符下一位开始继续往下找，已经确定不重复的就不用重复比较了。
就字符串 “abcdcabc” 为例，查找思路如下：
1、从 a 开始往后寻找
当找到第5个字符 c 时，发现和第3个字符 c 重复，结束。
此时以第1个字符 a 开头的最长不重复字符串就是 abcd 。
2、如果按照暴力查找的思路，接下来就是从第2个字符 b 开始，寻找以第2个字符 b 为开头的最长不重复字符串。
当找到第5个字符 c 时，此时发现又和第3个字符 c 重复，结束。
此时以第2个字符 b 开头的最长不重复字符串就是 bcd 。
3、到这里，可以发现，步骤2的遍历是不必要的，因为中间字符串 bcd 不重复是被验证过的；而且当找到第5个字符 c 后，也必然和第三个字符 c 重复，这也是被验证过的。
所以在图中两个红色 c 字符之前的字符，在验重的时候，在这里都会因为重复而停止。
那么其实可以得出结论，当发现第三个字符 c 和 后面字符重复时，那么以第2个字符 b 为开头的最长不重复字符串，以第3个字符 c 为开头的最长不重复字符串，其长度都不会超过以第1个字符 a 为开头的最长不重复字符串。
那么 c 之前的查找也就没有必要了，可以直接从 c 后面的字符为开头进行查找。
4、根据步骤3发现的结论，我们设定不重复区间起始字符位置 start = 0，结束字符位置 end = 0，最长串长度 max = 0，可以得出如下步骤：
到此就结束了，实际上发现，以 end 为基数，进行一次循环遍历就可以找出最长字符串长度。
一、双重循环滑动窗口
Java 代码
class Solution {
public int lengthOfLongestSubstring(String s) {
int length = s.length();
int end = 0, max = 0;
HashSet<Character> occ = new HashSet<Character>();
for(int i = 0 ; i < length ; i ++){
if(i != 0){
occ.remove(s.charAt(i-1));
}
while(end < length && !occ.contains(s.charAt(end))){
occ.add(s.charAt(end));
end++;
}
max = Math.max(max, end - 1 - i + 1);
}
return max;
}
}
复杂度分析
执行结果
执行用时：6 ms
内存消耗：38.6 MB
通过测试用例：987 / 987
二、单层循环滑动窗口（优化）
Java 代码
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
// 记录字符上一次出现的位置
int[] last = new int[128];
// 窗口开始位置、最长不重复字符串长度
int start = 0, max = 0;
// 遍历字符，区间为 start -> i
for(int end = 0; end < n; end++) {
int endKey = s.charAt(end);
start = Math.max(start, last[endKey]);
max = Math.max(max, end - start + 1);
last[endKey] = i + 1;
}
return max;
}
}
复杂度分析
执行结果
执行用时：2 ms
内存消耗：38.4 MB
通过测试用例：987 / 987
💂 个人主页: 白纸君
🤟 版权: 本文由白纸君原创、在CSDN首发、需要转载请联系博主
💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦。
💅 有任何问题欢迎私信,看到会及时回复!
