https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
輸入: 字符串
處理: 尋找不包含重復(fù)字符的最長(zhǎng)子串
輸出: 最長(zhǎng)子串的長(zhǎng)度
思路:
1.左指針始終指向當(dāng)前子串的最左邊,
2.判斷當(dāng)前字符是否包含在當(dāng)前子串中,如果在,左指針等于前面重復(fù)字符的下標(biāo)+1,
3.否則繼續(xù)判斷下一位字符
4.記錄每次子串長(zhǎng)度的最大值
其中第2步,可以簡(jiǎn)化為 當(dāng)前左指針下標(biāo) 和 重復(fù)字符下標(biāo)+1 的最大值,因?yàn)? 如果當(dāng)前字符不包含在當(dāng)前子串中,而是在子串之前,求個(gè)最大值,也沒什么不妥,代碼看起來(lái)簡(jiǎn)潔很多.
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int max=0;
int left=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(map.containsKey(c)){
left=Math.max(left,map.get(c)+1);
}
max = Math.max(max,i-left+1);
map.put(c,i);
}
return max;
}
}
