无重复字符的最长子串
1.题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。2.我的题解
2.1思路
对于给定的字符串，定义一个指针i
从0开始往右滑动
判断第i个字符是否在i的左侧出现过
如果没有出现过
记录下此时0到i的值l
如果发现有重复的字符m了
先找到m这个字符在左侧出现的位置x
然后删掉从0到x位置的左右字符，包括x
对比l和（i-x）的大小，取较大者赋值给l
直到i走到最右端
l即为解
时间复杂度为O(n)
空间复杂度为O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。
2.2图解
计算完第一个字符，目前无重复字符的最长子串是a，所以l=1
计算完第二个字符，目前无重复字符的最长子串是ab，所以l=2
计算完第三个字符，目前无重复字符的最长子串是abc，所以l=3
计算完第四个字符，删除a，以及a之前的字符，目前无重复字符的最长子串是bca，所以l=3
计算完第五个字符，删除b，以及b之前的字符，目前无重复字符的最长子串是cab，所以l=3
计算完第六个字符，删除c，以及c之前的字符，目前无重复字符的最长子串是abc，所以l=3
计算完第七个字符，删除b，以及b之前的字符，目前无重复字符的最长子串是cb，所以l=2
计算完第八个字符，删除b，以及b之前的字符，目前无重复字符的最长子串是b，所以l=1
l取最大值，就是3
2.3 代码1
class Solution {
public int lengthOfLongestSubstring(String s) {
StringBuilder stringBuilder = new StringBuilder();
int l = 0;
for (int i = 0; i < s.length(); i++) {
String c = String.valueOf(s.charAt(i));
if (stringBuilder.indexOf(c) >= 0) {
stringBuilder.delete(0, stringBuilder.indexOf(c) + 1);
}
stringBuilder.append(c);
l = Math.max(stringBuilder.length(), l);
}
return l;
}
}
时间复杂度还算满意
但是为什么内存消耗才击败了5%的用户？
不能忍
我以为是循环里边有个字符串局部变量的定义和操作造成的
于是尝试第二种方法
将循环内的String变量定义给去掉了
2.4 代码2
class Solution {
public int lengthOfLongestSubstring(String s) {
StringBuilder sb = new StringBuilder(s);
int l = 0, i = 0;
while (i < sb.length()) {
int x = sb.indexOf(String.valueOf(sb.charAt(i)));
if (0 <= x && x < i) {
sb.delete(0, x + 1);
i = i - x - 1;
} else {
i++;
}
l = Math.max(l, i);
}
return l;
}
}
没想到耗时上去了，内存消耗纹丝未动
不能忍
我又以为是新定义了一个Stringbuilder造成的
于是将StringBuilder变量去掉了，值保留输入的String
又测试了下边的这个代码3
2.5 代码3
class Solution {
public int lengthOfLongestSubstring(String s) {
int l = 0, i = 0;
while (i < s.length()) {
int x = s.indexOf(s.charAt(i));
if (0 <= x && x < i) {
s = s.substring(x + 1);
i = i - x - 1;
} else {
i++;
}
l = Math.max(l, i);
}
return l;
}
}
结果内存消耗没有下来
执行时间反而慢了好多倍
虽然不能忍
但是我也没其他想法了
3. 他山之石可以攻玉
自己没本事就多学习吧
3.1 最受欢迎的解法
于是我找到了leetcode上最受欢迎的Java解法
思路
【滑动窗口】
暴力解法时间复杂度较高，会达到 O(n^2)，故而采取滑动窗口的方法降低时间复杂度
定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start，结束位置为 end
随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
无论是否更新 start，都会更新其 map 数据结构和结果 ans。
时间复杂度：O(n)
具体代码实现如代码4
代码4
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int end = 0, start = 0; end < n; end++) {
char alpha = s.charAt(end);
if (map.containsKey(alpha)) {
start = Math.max(map.get(alpha), start);
}
ans = Math.max(ans, end - start + 1);
map.put(s.charAt(end), end + 1);
}
return ans;
}
}
虽然执行的耗时比我的方法快了一点点
但是内存消耗还是这样，并没有得到提升
3.2 官方解法
人在屋檐下，不得不低头
学学人家官方的大佬吧
思路
使用「滑动窗口」来解决这个问题了：
我们使用两个指针表示字符串中的某个子串（的左右边界）。其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 r_krk；
在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
在枚举结束后，我们找到的最长的子串的长度即为答案
时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)[0,128) 内的字符，即∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)
代码5
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
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;
}
}
你是官方啊
就这点水平？？？
4. 总结
这道题虽然不难
但是管中窥豹，发现需要注意的地方还是有很多的
Java中String的操作相对StringBuilder()来说是非常耗时的
查看Java源码可以看到
你对String的每一次操作，都是new了一个String
算法也许没有最优的
要么时间换空间
要么空间换时间
优化都是在出现问题的时候要做的取舍操作
最后，我还是想知道把我击败的95%的大佬是怎么干的
各位大佬谁能给我点提示？
文/戴先生@2020年6月16日
---end---