(记录自己的leetcode之旅)
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
自己解法：
public static int lengthOfLongestSubstring(String s) {
if("".equals(s))
return 0;
int len = 1;
for(int i=0;i<s.length()-1;i++){
for(int j=i+1;j<s.length();j++){
String sonStr = s.substring(i,j).toString();
String charStr = s.substring(j,j+1).toString();
if(sonStr.indexOf(charStr) >= 0){
len = Math.max(len, sonStr.length());
break;
}else{
len = Math.max(len, sonStr.length()+1);
}
}
}
return len;
}
最佳解法：
public static int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
int len = 0;
for(int i=0,j=0;j<s.length();j++){
if(map.containsKey(s.charAt(j))){
i = Math.max(map.get(s.charAt(j)) + 1, i);
}
len = Math.max(len, j-i+1);
map.put(s.charAt(j), j);
}
return len;
}
en.我的暴力破解还是不说了，分析一下最佳解法。
map的<key,value>存的<字符，下标>。i是子串开头，j是字串结束。遍历字符串的过程中，"len = Math.max(len, j-i+1);"是获得两个字符之间的长度。
关键点在于中断遍历的if判断语句，if语句里面的内容是 遇到重复的字符时更改i的值。改为多少呢？
遇到重复的字符之后，让i = map.get(s.charAt(j)) + 1不就好了;结果报错，"abba"为报错例子。因为字符串是从左往右走的，自然更改的值不能比i本身再小。所以加上max即可。
