1. 题目给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
由英文字母、数字、符号和空格组成
2. 思路一
对于这种题，第一眼肯定是暴力啦。两个for循环，一个用来循环遍历寻找该字串的起点，一个用来遍历子串的最大长度。我的思路是用一个List<Character>把一个子串的每个char存起来，然后遍历所有可能的子串，最后看所有的List<Character>中，谁的size最大，就是最长子串。代码如下：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Solution {
public int lengthOfLongestSubstring(String s) {
List<List<Character>> all = new ArrayList<>();
for (int j = 0; j < s.length(); j++) {
List<Character> subList = new ArrayList<>();
for (int i = j; i < s.length(); i++) {
Character ss =s.charAt(i);
if(!subList.contains(ss)){
subList.add(ss);
}else{
break;
}
}
all.add(subList);
}
all.sort(Comparator.comparing(List<Character>::size).reversed());
return all.size() > 0 ? all.get(0).size() : 0;
}
}
暴力的方法不用说都知道结果比较惨烈：
3. 思路二
其实仔细想想，上面这种暴力不仅时间复杂度是，空间复杂度也是，堪称工程算法。对于这种类似字符串求最短的，之前也配到过，用的是滑动窗口算法。也就是固定左边，用右边去遍历字符串，当右边碰到与左边一样的字符，就让左边等于右边此时的位置，此时原来左边的位置和当前左边的位置就代表了这个区间的字符字串的长度。这样，当每次左边与右边字符相等时，我们比较一下原有的字符字串和当前的字符字串，选择一个较大的，最终就能获取到最长的字符字串。代码如下：
public static int lengthOfLongestSubstring(String s) {
if (s.length() <= 1){
return s.length();
}
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0){
occ.remove(s.charAt(i - 1)); // 左指针向右移动一格，移除一个字符
}
while (rk + 1 < n && !occ.contains(s.charAt(rk+1))){
// 不断地移动右指针
occ.add(s.charAt(rk+1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
上述算法其实并不是最优的，由于使用了Set结构，因此空间上并无优势。看到一种更为简单快速的滑动窗口算法如下,这是使用数组来标识是否已经访问过该字符。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
int[] last = new int[128];
for(int i = 0; i < 128; i++) {
last[i] = -1;
}
int n = s.length();
int res = 0;
int start = 0; // 窗口开始位置
for(int i = 0; i < n; i++) {
int index = s.charAt(i);
start = Math.max(start, last[index] + 1);
res = Math.max(res, i - start + 1);
last[index] = i;
}
return res;
}
}
该算法战绩：
4. 总结
此题主要考察滑动窗口，在Lettcode中不算难题，只要多练习，就可以解题。滑动窗口算法在很多地方都有应用，应该多学习。
评论区