题目
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.
我的解答
public int lengthOfLongestSubstring(String s) {
if(s == null)
return 0;
boolean[] flag = new boolean[256];
int result = 0;
int start = 0;
char[] arr = s.toCharArray();
for(int i=0;i<s.length();i++){
char current = arr[i];
if(flag[current]){
result = Math.max(result, i-start);
for(int k=start;k<i;k++){
if(arr[k] == current){
start = k+1;
break;
}
flag[arr[k]] = false;
}
}else{
flag[current] = true;
}
}
result = Math.max(arr.length-start, result);
return result;
}
分析
这题同样要求O（N）的时间复杂度。我们把目前引入一个bool数组，用来标记这个字母是否出现过。引入一个start指针和current指针，current目前指到的位置如果在flag数组中为true，则出现了重复字母，现在需要更新start的位置，因为原先的start->重复字母的第一个这段一定小于等于当前的current-start这段，所以不需要再计算从start+1开始的字符串，直接从重复字母+1的地方开始就可以，同时把start位移过程中的这些值都置为false。
