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.
給定一個(gè)字符串默垄，找出其中不含重復(fù)字母的最長(zhǎng)子串（注意不是子序列）瞻凤，返回它的長(zhǎng)度。
思路
字母查重：構(gòu)建一bool列表逢并，存儲(chǔ)當(dāng)前子串中是否含有某字母嘁字。
設(shè)置兩指針i和j椅野，分別表示子串頭尾幻捏，j向后掃描宏所，每次進(jìn)行查重，保存當(dāng)前子串長(zhǎng)度壹堰，遇重復(fù)字母則i移動(dòng)到此字母第一次出現(xiàn)的下一個(gè)位置拭卿，并將移除子串的字母進(jìn)行查重表更新。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i=0,j=0;
int n=s.size();
int maxlen=0;
bool exist[256]={false};
while(j<n){
if(exist[s[j]]){
maxlen=max(maxlen,j-i);
while(s[i]!=s[j]){
exist[s[i++]]=false;
}
++i;
++j;
}
else{
exist[s[j++]]=true;
}
}
maxlen=max(maxlen,n-i);
return maxlen;
}
};
也可使用HashMap存儲(chǔ)字符出現(xiàn)的位置贱纠，若存在則取同一個(gè)字符兩個(gè)位置的距離峻厚，若不存在則記錄字符的位置。
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int res=0;
for (int i=0, previous=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
previous = Math.max(previous,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
res = Math.max(res,i-previous+1);
}
return res;
}
}
