難度：中等
給定一個(gè)字符串堰怨，請你找出其中不含有重復(fù)字符的 最長子串 的長度遥昧。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"俭缓，所以其長度為 1刑赶。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"捏浊，所以其長度為 3。
請注意撞叨，你的答案必須是 子串 的長度金踪，"pwke" 是一個(gè)子序列，不是子串牵敷。
第一種解答：
思路：
使用一個(gè)長度為 128 的 boolean 數(shù)組 flag 充當(dāng)散列表用來記錄子串的字符（利用到字符的 ascii 碼作為數(shù)組的下標(biāo)）胡岔，初始化都為false。遍歷整個(gè)字符串枷餐，外循環(huán)控制子串的起始靶瘸，內(nèi)循環(huán)控制子串的長度，每遇到一個(gè)字符就檢查 flag 中是否存在該元素，不存在則將 flag[]設(shè)置為 true怨咪，存在則結(jié)束內(nèi)循環(huán)屋剑。
class Solution {
public int lengthOfLongestSubstring(String s) {
boolean[] flag = new boolean[128]; // 問題1
int sublen = 0;
for(int i = 0; i < s.length(); i ++){
// 將 flag 初始化為 false
for(int k = 0; k < flag.length; k++)
flag[k] = false;
// 子串的起始
flag[(int)(s.charAt(i))] = true;
int len = 1;
for(int j = i+1; j < s.length(); j ++){
// flag 中存在相同字符的情況
if(flag[(int)(s.charAt(j))])
break;
// flag不存在相同字符的情況
len ++;
flag[(int)(s.charAt(j))] = true;
}
if(sublen < len){
sublen = len;
}
}
return sublen;
}
}
也可將 boolean 數(shù)組換成 int 數(shù)組，數(shù)組記錄的是元素所在的下標(biāo)诗眨。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals("")) return 0;
int[] flag = new int[128];
int sublen = 0 ,len;
for(int i = 0; i < s.length(); i ++ ){
// 初始化 flag;
for(int k = 0; k < flag.length; k++)
flag[k] = -1;
flag[s.charAt(i)] = i;
len = 1;
for(int j = i + 1; j < s.length(); j ++){
if(flag[s.charAt(j)] != -1){
i = flag[s.charAt(j)];
break;
}
len ++;
flag[s.charAt(j)] = j;
}
sublen = len > sublen ? len: sublen;
}
return sublen;
}
}
參考評論區(qū)的第二種解答
第二種解答：
使用雙指針 left, right維護(hù)一個(gè)無重復(fù)字符區(qū)間（left 與 right 之間的字符無重復(fù)）唉匾，right 指針每移動(dòng)到一位，就循環(huán)檢測 [left , right) 無重復(fù)字符區(qū)間是否存在與 right指向的字符相同的字符匠楚，如果存在就更新 left 指針巍膘，將 left移動(dòng)到區(qū)間中與right指向相同字符的下一個(gè)位置，繼續(xù)維護(hù)一個(gè)無重復(fù)的字符區(qū)間芋簿，同時(shí)更新最長子串的長度max峡懈。不存在則更新最長子串的長度max，同時(shí)繼續(xù)將 right 往下移動(dòng)益咬。
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0, left = 0, right = 0;
if(s.length() == 1)
max = 1;
else if( !s.equals("") ){
//char[] str = s.toCharArray();
for(right = 1; right < s.length(); right ++){
for(int i = left; i < right; i ++){
if(s.charAt(i) == s.charAt(right)){
// 更新 max
max = right - left > max ? right - left : max;
left = i + 1;
break;
}
}
// 更新 max
max = right- left + 1 > max ? right - left + 1: max;
}
}
return max;
}
}
