題目
給定一個(gè)字符串嫉拐，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"税娜，所以其長(zhǎng)度為 3坐搔。
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1敬矩。
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"概行，所以其長(zhǎng)度為 3。
請(qǐng)注意弧岳，你的答案必須是 子串 的長(zhǎng)度占锯，"pwke" 是一個(gè)子序列，不是子串缩筛。
解答
第一種
//1、窮舉堡称，從第一個(gè)字符開(kāi)始瞎抛，一次向后遍歷，如果有相同字符却紧，記錄長(zhǎng)度桐臊。
//2、繼續(xù)從第二個(gè)字符晓殊，重復(fù)1步驟断凶，比較長(zhǎng)度，留下最長(zhǎng)的
//3巫俺、重復(fù)2认烁，返回最長(zhǎng)result
public static int lengthOfLongestSubstring(String s) {
int length = s.length();
int result = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j <= length; j++) {
//
if (unique(s,i,j)) {
result = Math.max(result, j - i);
}
}
}
return result;
}
public static boolean unique(String s,int i, int j){
HashSet<Character> strings = new HashSet<>();
for (int k = i; k < j; k++) {
char c = s.charAt(k);
if (strings.contains(c)){
return false;
}else{
strings.add(c);
}
}
return true;
}
第二種(滑動(dòng)窗口)
public static int lengthOfLongestSubstring2(String s) {
int length = s.length();
HashSet<Character> characters = new HashSet<>();
int result = 0, i = 0, j = 0;
while (i < length && j <length){
if (!characters.contains(s.charAt(j))){
characters.add(s.charAt(j));
j++;
result = Math.max(result,j-i);
}else{
characters.remove(s.charAt(i));
i++;
}
}
return result;
}
分析
1、 第一種方式，時(shí)間復(fù)雜度 n3,這種方式在實(shí)際情況下是不可取的却嗡。
2舶沛、時(shí)間復(fù)雜度：O(2n) = O(n)O(2n)=O(n)，在最糟糕的情況下窗价，每個(gè)字符將被 ii 和 jj 訪問(wèn)兩次如庭。空間復(fù)雜度：O(min(m, n))O(min(m,n))撼港，與之前的方法相同坪它。滑動(dòng)窗口法需要 O(k)O(k) 的空間帝牡，其中 kk 表示 Set 的大小往毡。而 Set 的大小取決于字符串 nn 的大小以及字符集 / 字母 mm 的大小。
