本文由作者三汪首发于简书。
历史解题记录已同步更新github.
题目
Problem Description:
Given a string, find the length of the longest substring without repeating characters.
Examples:
- Given
"abcabcbb", the answer is"abc", which the length is 3. - Given
"bbbbb", the answer is"b", with the length of 1. - Given
"pwwkew", the answer is"wke", with the length of 3.
Note that the answer must be a substring,"pwke"is a subsequence and not a substring.
题目分析
题意是让我们返回给定字符串不含重复字符的最大子字符串的长度。
代码和思路
我会对自己的原始提交版本做个记录。
没耐心看的同学可以跳过原始版本直接去看后面的B和C，
分别是我对当前Java solution最优解的分析和我自己的改进版本。
A.原始版本
看到这个题目的时候，我是把它当成字符串处理题来做的。
没注意看题目要求返回的是符合要求的最大子字符串长度。
因此第一个版本做了很多字符处理，Runtime也很感人，用了90ms,排位在12.61%的位置。
1.0版本代码如下：
private int lengthOfLongestSubstring_1_0(String str){
if (str==null || str.equals("")) {
return 0;
}
String[] subs = new String[str.length()];
int subsIndex = 0;
String[] chars = str.split("");
StringBuffer sb = new StringBuffer(chars[0]);
for (int i = 1; i < chars.length; i++) {
if (!sb.toString().contains(chars[i])) {
sb.append(chars[i]);
}else if(sb.indexOf(chars[i]) != sb.length()-1){
subs[subsIndex++] = sb.toString();
sb.delete(0,sb.indexOf(chars[i])+1);
sb.append(chars[i]);
}else{
subs[subsIndex++] = sb.toString();
sb.delete(0, sb.length());
sb.append(chars[i]);
}
}
subs[subsIndex++] = sb.toString();
int maxLength = subs[0].length();
for (int i = 1; i < subs.length; i++) {
if (subs[i] == null) {
return maxLength;
}
if (subs[i].length() > maxLength) {
maxLength = subs[i].length();
}
}
return maxLength;
}
思路分析：
这段代码的思路是先把给定字符串分解成单个字符数组，再依次写入StringBuffer。
当出现重复字符时，根据重复字符在字符串中的位置分两种情况处置。
情况一、重复字符不是当前字符串的最后一个字符时：
将当前StringBuffer中拼好的字符串写入String[]数组，删除从字符串开端到重复字符位置的所有字符，从重复字符的后一个字符为字符串的开端，继续拼接字符串。
情况二、重复字符是当前字符串的最后一个字符时：
将当前StringBuffer中拼好的字符串写入String[]数组，清空StringBuffer,重新开始新的字符串拼接。
最后遍历String[]数组，获取长度最大的字符串的长度并返回。
不足之处：
在这个版本的代码中我有一个很大的弊病是我忘了String可以字节调用.toCharArray()方法获取char[]数组，而是用了.split("")来把给定字符串分割成一个个由单个字符组成的字符串。
B.改进版本
改进版本不再使用字符串拼接的方法来实现。
而是使用一个快指针(Runner)和一个慢指针(Walker)来遍历由给定字符串分解的char[]数组，直接获取最大子字符串长度。
这种方式Runtime只有36ms,排位在99.94%的位置。
值得一提的是，这个改进版本是在看了一会儿会分析的当前Java最优解以后结合自己思考而来的。
我通过写自己的改进版来理解最优解的代码思路。这是一个小心得，你也可以试试。
1.1版本代码如下：
private int lengthOfLongestSubstring_1_1(String str){
//It's my own habit to check if the input is empty.
if (str == null) {
return 0;
}
char[] chars = str.toCharArray();
if (chars.length<2) {
return chars.length;
}
int maxLength = 0,spliter = 0;
for (int i = 1; i < chars.length; i++) {
for (int j = spliter ; j < i ; j++) {
if (chars[i]==chars[j]) {
int tempLength = i-spliter;
maxLength = maxLength > tempLength ? maxLength : tempLength;
spliter = j+1;
break;
}
}
}
maxLength = maxLength > chars.length-spliter ? maxLength : chars.length-spliter;
return maxLength;
}
思路分析：
- 当给定字符串长度小于2时，直接返回它的长度。
- 使用快指针和慢指针遍历给定字符串分解而来的char[]数组
2.1 使用spliter来记录重复字符的下一个字符的位置（重复字符和它前面的字符对新子字符串没有意义），初始值为0。
2.2 使用maxLength来记录每次遍历时子字符串的最大长度。当有新的最大子字符串产生（遇到重复字符或结束遍历）时，判断其长度是否大于maxLength。若是，则更新maxLength。 - 我不知道我真的解释清楚了没，虽然我觉得我解释清楚了。如果正在看的你哪里不理解，欢迎留言讨论：）
C.截至此刻LeetCode上用时最少的Java Solution
代码如下：
/**
*
* <p>
* Description:The best solution on LeetCode by this time.<br />
* Runtime:35ms<br />
* </p>
* @version 0.1 2017年12月8日
* @param s
* @return
* int
*/
private int lengthOfLongestSubstring_best(String s) {
char[] chars = s.toCharArray();
if(2 > chars.length){
return chars.length;
}
int max = 0;
int split_at = 0;
int cur_len = 1;
for(int i=1;i<chars.length;i++){
int j = split_at;
for(;j<i;j++){
if(chars[i] == chars[j]){
break;
}
}
if(j < i){
split_at = j+1;
cur_len = i-j;
}else{
cur_len++;
}
if(cur_len > max) max = cur_len;
}
return max;
}
思路分析：
- 主体思路同改进版本思路，下面来讲一些细节方面的不同。
- 使用cur_len字段来记录当前子字符串长度，初始值为1。
使用split_at字段来记录上一次碰到的重复字符的下一个字符的位置，初始值为0。
使用max字段记录每次遍历时子字符串的最大长度。 - 当出现重复字符时，break跳出快指针循环（即内层for循环，快指针为j）。
结束内层for循环以后，判断快指针与慢指针（慢指针为i）是否相等。
当出现重复字符时，快指针与慢指针是不会相等的。因为会break跳出循环。
3.1 若快指针与慢指针相等，则当前子字符串没有遇到重复字符。cur_len自增。
3.2 若快指针小于慢指针，则不含重复字符的当前子字符串长度为cur_len=i-j，更新split_at字段。
3.3 快指针不可能大于慢指针。因为内层for循环条件是j<i。 - 每次结束外层循环时，判断cur_len是否大于max。若是，则更新max。
- 我不知道我真的解释清楚了没，虽然我觉得我解释清楚了。如果正在看的你哪里不理解，欢迎留言讨论：）
以上。
希望我的文章对你能有所帮助。
我不能保证文中所有说法的百分百正确，
但我能保证它们都是我的理解和感悟以及拒绝直接复制黏贴（确实需要引用的部分我会附上源地址）。
有什么意见、见解或疑惑，欢迎留言讨论。
