1.题目
给定一个字符串
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
由英文字母、数字、符号和空格组成
2. 解题思路
结合题目要求和示例我们可以暂时汇总:
- 字符串长度可以为0。
- 要计算不重复的子串,同时比较谁最长。输出最长的值就可以了。
- 字符串里面有数字,字面和空格。
暴力破解方法就是拿当前字符和后面的字符一个一个比较,如果中间有重复的。我们就移动下一位继续比较。
然后将数值计算,判断谁大。
示例:
输入: s = "abcabcbb"
第一局:ab,abc,abca失败 长度为3
第二局:bc,bca,bcab失败 长度为3
第三局:ca,cab,cabc失败,长度为3
第四局:ab,abc,abcb失败,长度为3
第五局:bc,bcb失败,长度为2
第六局:cb,cbb 失败,长度为2
第七局:bb失败,长度为0
最大长度为:3
我们如果直线思维,通过字符串添加和移除的逻辑书写代码:
示例1:
public int lengthOfLongestSubstring(String s) {
int i = -1;//在字符串中的下标
StringBuilder builder = new StringBuilder();
int size=0;
if (s.length() != 0) {
for (char t : s.toCharArray()) {
i = builder.indexOf(t + "");
if (i != -1) {
builder.delete(0, i+1);
}
builder.append(t);
if (size < builder.length()) {
size = builder.length();
}
}
}
return size;
}
我们将字符串存到StringBuilder中,然后一点点判断是否有下标。如果有就从0到该位置的字符进行删除,然后再添加新的字符,进行比较。上面的代码理解很简单,但是执行速度和效率就不行了。
花费了11毫秒,只击败了20.63%
结果出来了,但是效率并不满意。我们继续优化。
除了粗暴的字符串拼接,有没有更好的解决思路呢?官方提供了一个参考示例:
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;
}
}
使用哈希集合记录字符,然后移动哈希集合的左右指针位置。
我们可以看到,内存占用没有太大变化,但是耗时得到了很大提升。
之后发现有大神出的更快版本,采用int 256来替换map。妙啊。
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxSize = 0;
int [] dict = new int[256]; //记录ASCII 码字符出现的位置,以字符作为下标
int base = 0;
int key = 0;
int i=0;
while(key < s.length()){
i = s.charAt(key);
if(dict[i] > base)
base = dict[i];
dict[i] = key+1; //以1作为起始位置,下标加1
maxSize = (maxSize>key-base+1)?maxSize:key-base+1;
key++;
}
return maxSize;
}
}
速度得到了完全的提升。下面详细介绍该方法的思路。
2.1 ASCII 字符方案详解
我们一行一行代码,来分析ASCII 字符解决方案为什么可以成功。
public int lengthOfLongestSubstring(String s) {
int maxSize = 0; //用来存储最长的子串的长度。
//创建一个256位的Int对象。
int [] dict = new int[256]; //记录ASCII 码字符出现的位置,以字符作为下标,
int base = 0; // 当前指针计算的起始位置
int key = 0; //指针位置,也就是当前比较的字符串的下标位置。
int i=0; //当前字符的ASCII值。
while(key < s.length()){ //下标只要小于字符串长度,我们就继续循环
//字符串可以直接转为Char[]。 我们通过下标获取当前的Char对象的int 也就是ASCCII码。
i = s.charAt(key); //例如a 的ASCII码为97。
if(dict[i] > base) // 检测当前数组该位置上是否有值,前面没有循环到的字符,该位置为0
base = dict[i];
dict[i] = key+1; //以1作为起始位置,下标加1。
maxSize = (maxSize>key-base+1)?maxSize:key-base+1; //判断新字符串长度有没有超过最大的,有就用新的,没有就还是保持最大值
key++; //下标加1 进入下一个循环。一直到字符串循环结束
}
return maxSize; //输出结果
}
问题1: 为什么Int 的字符长度设置为256?
题目中说了,s 是由英文字母+数字+符号+空格组成。它们的ASCII值分别是:
0~31 和127 :为各种控制字符,例如换行,回车,删除,制表符,等
32:为空格。
48~57:为0到9十个阿拉伯数字。
65~90:为26个大写英文字母。
97~122:为26个小写英文字母。
之后的就是各种符号了,全部的值就是256种。所以我们int的数组长度要定义为256
否则会出现下标越界。
问题2:base值为什么是key+1?
因为每次给base赋值的时候,就代表当前出现了重复字段了。所以计算字符长度就要从key+1开始计算
问题3:dict[i] = key+1 为什么要+1呢?
因为,默认字符长度都是从1开始的。而循环中key是从0开始的。不加1的话,就短了。
而最终判断的maxSize 就是比较当前的位置-开始位置然后+1 得到的子字符串长度。
参考资料
题目来源于LeetCode :3. 无重复字符的最长子串 - 力扣(LeetCode) (leetcode-cn.com)
评论区