无重复字符的最长子串
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%的大佬是怎么干的
各位大佬谁能给我点提示?
---end---
题目和部分代码来源于:力扣(LeetCode)
更多精彩推荐
文/戴先生@2021年11月15日