题目LeetCode-无重复字符的最长字串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
- 示例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 示例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
分析与实现
解法一
- 分析
这里面的难度在于，从i开始遍历，遇到相同字符后结束，记录长度。然后从i+1开始继续遍历 - 实现（java）
/**
* 求不出现重复的最大字串的长度
* @param s 源串
* @return 长度值
*/
public static int lengthOfLongestSubstring(String s) {
if (s.length() < 2) {
return s.length();
}
int maxLen = 0;
List<Character> list = new ArrayList<>();
for (int i = -1; i < s.length(); i++){
list.clear(); // 每次清空map
//list.add(s.charAt(i));
for (int j = i+1; j < s.length(); j++) {
Character c = s.charAt(j);
if (!list.contains(c)){
list.add(c);
}else{
// 说明存在了
break;
}
}
if (list.size() > maxLen) {
maxLen = list.size();
}
}
return maxLen;
}
这里使用了list作为字串的存储，主要是便于判断字符的存在情况，用了两次for循环
这样做的确可以达到效果，但是时间复杂度很大，提交结果如下
解法一
解法二
-分析
在每一次遍历到一个重复的字符时，其实在这之前的所有字符已经遍历，那么应该可以直接拿来用，所以这里分为三种情况：
- 情况1: 重复字符出现在子串的第一位；
- 情况2: 重复字符出现在子串的中间；
- 情况3: 重复字符出现在子串的最后；
关于这三种情况的处理详细见下面的代码中的注释分析：
- 实现（java）
if (s.length() < 2) {
return s.length();
}
int maxLen = 0;
List<Character> list = new ArrayList<>();
for (int j = 0; j < s.length(); j++) {
Character c = s.charAt(j);
if (!list.contains(c)){
list.add(c);
}else{
int index = list.indexOf(c); // 得到列表中该字符的下标
/*
1. 如果下标在最开始
判断list的size和max的大小
将第一个remove掉
将新的字符加入list
*/
if (index == 0){
if (list.size() > maxLen) {
maxLen = list.size();
}
list.remove(0);
}
/*
2. 如果下标在最中间
判断前面部分的长度是否大于当前的maxlen，如果是修改maxlen
将index出之前(包括index出的字符)删除
将j处的字符加入list
*/
else if (index != 0 && index != (list.size() - 1)) {
if (list.size() > maxLen) {
maxLen = list.size();
}
for (int i = 0; i < index + 1; i++) {
list.remove(0); // 移除index+1次；list的remove问题
}
}
/*
3. 如果下标在最最后
判断size和maxlen的大小
清除list中所有的元素
将j处的字符加入
*/
else {
if (list.size() > maxLen) {
maxLen = list.size();
}
list.clear();
}
list.add(c);
}
}
if (list.size() > maxLen) { // 判断最后list中的字串长度
maxLen = list.size();
}
return maxLen;
这样处理后，在时间复杂度上好了很多！
image
当然LeetCode上还有很多大佬的实现，时间复杂度还要低，但是
思想都是重复利用遍历过序列
最后
此致，敬礼！
