题目要求找出一个字符串中最长的没有重复字符的子串长度。如pwwkew中的不含重复字符的最长子串为wke(kew也行)，长度都为3。
不过最后一个用例的长度有点蛋疼。。开始的O(n2)的算法就超时了。
最暴力的解法
这个很容易想到，既然你要求不含重复字符的最长子串，那我把所有满足要求的子串都求出来，最后求个最大值就可以了。
因为没有空间限制，这里存储用了一个Set来保证不重复
public int lengthOfLongestSubstring(String s) {
int start, end, index = 0;
int[] result = new int[s.length()];
// 用来存储字符，判重
Set<Character> set = new HashSet<>();
// 找出所有子串
for (int i = 0; i < s.length(); i++) {
start = i;
end = i;
for (int j = i; j < s.length(); j++) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
end++;
} else if (set.contains(s.charAt(j))){
// 将字符串的长度存到一个数组里，最后对这个数组求最大值
result[index++] = end - start;
set.clear();
break;
}
if (j == s.length() - 1) {
result[index++] = end - start;
set.clear();
}
}
}
// 求最大值部分
int max = 0;
for (int i = 0; i < result.length; i++) {
if (result[i] > max) {
max = result[i];
}
}
return max;
}
改良的解法
然后怨念的超时了。。在看那个超长的用例的时候突然想到字符最多也就那么常数个，并不需要遍历到字符串尾部，于是把代码改为
public int lengthOfLongestSubstring(String s) {
int start, end, index = 0;
int[] result = new int[s.length()];
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
// 下面一部分代码用来找本字符下一次出现的位置，如果后面没有再出现了，则遍历到字符串末尾
int t1 = 0;
if (s.lastIndexOf(s.charAt(i)) == i) {
t1 = s.length();
} else {
t1 = s.indexOf(s.charAt(i), i + 1);
}
start = i;
end = i;
for (int j = i; j < t1; j++) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
end++;
} else if (set.contains(s.charAt(j))){
result[index++] = end - start;
set.clear();
break;
}
if (j == t1 - 1) {
result[index++] = end - start;
set.clear();
}
}
}
int max = 0;
for (int i = 0; i < result.length; i++) {
if (result[i] > max) {
max = result[i];
}
}
return max;
}
代码没有太大变化，应该也比较好懂。
Solution
虽然AC了，但看看这代码丑得不行，一定有更好的解法，去Solution翻翻，看到Java分类下有两个不错的解法
一、利用256大小的整型数组
public int lengthOfLongestSubstring(String s) {
int[] mOccur = new int[256];
int maxL = 0;
for(int i = 0, j = 0; i < s.length(); ++i){
char ch = s.charAt(i);
++mOccur[ch];
while(mOccur[ch] > 1){
--mOccur[s.charAt(j++)];
}
maxL = Math.max(maxL, i - j + 1);
}
return maxL;
}
因为ASCII码总共256个，借用一个256大小的整型数组，Java里如果没有给整型赋值，那么它的默认值是0，开始从头开始遍历这个字符串，把这个字符转换成十进制数作为index，再将mOccur[index]加1，也就是此时该位置的数不为0。如果加1后该数字大于1，那么说明这个字符已经出现过了一次，一次不含重复字符的子串到这里结束了。这段代码里 j 变量的意义是不含重复字符的最长子串的起始坐标，所以当mOccur[index]的值大于1时，需要将j向后挪一个位置。除此之外，每次循环都会更新一次最大值。
二、HashMap来存储字符和位置
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
这种方法j一样用于表示不含重复字符的最长子串的起始位置，每次发现一个重复元素时，取决于上一个相同字符的位置temp和j谁比较大，如果temp < j，那么也不用管它，我们的起始位置已经是j了，如果j比较大的话，移动到j的下一个位置
