題目描述
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
即給定一個字符串氓奈，返回最長的沒有重復(fù)字符的子串的長度
思路
用一個HashMap來存儲字符串遇汞。其中key為字符臭蚁，value為該字符在字符串中的位置瞧捌。
使用兩個指針i，j來指示最長子串的位置义黎。剛開始i禾进，j都為0，指向第一個字符廉涕。然后i開始向右遍歷泻云。若遍歷到的字符已在HashMap中，則更新它的value為現(xiàn)在i的位置狐蜕。并且將j指向該字符的下一個位置（j只能往右移宠纯，或者不移，不能左移）馏鹤。若未在HashMap中征椒，則將該字符以及它的位置放入HashMap中。最大的（i-j+1）即為最長子串的長度湃累。
代碼如下
public class Solution {
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;
}
}
