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.
题目中主要是要统计子串的长度,这样的子串要满足一个条件就是子串中没有重复的元素。要实现快速的查找,比较方便的是使用Hash表的结构。
在查找到相同字符的时候要删除掉相同字符前面的所有字符。所以要做好子串的第一个字符的下标的保存。
public static int lengthOfLongestSubstring(String s) {
//利用hash表
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int length = map.size();
int lenTmp = map.size();
char c[] = s.toCharArray();// 将字符串转换为字符数组
int start = 0;
for (int i = 0; i < c.length; i++) {
if (map.containsKey(c[i])) {
int j = start;
while (c[j] != c[i]){
map.remove(c[j]);
j++;
}
map.remove(c[j]);
start = j+1;
map.put(c[i], i);
} else {
map.put(c[i], i);
}
lenTmp = map.size();
length = (length < lenTmp) ? lenTmp : length;
}
return length;
}