回歸次數(shù)：1
題目：
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)肢预，非商業(yè)轉(zhuǎn)載請注明出處
給定一個字符串洼哎，請你找出其中不含有重復(fù)字符的 最長子串 的長度沼本。
示例：
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"锭沟，所以其長度為 3。
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"族淮，所以其長度為 1。
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"祝辣，所以其長度為 3贴妻。
請注意蝙斜，你的答案必須是 子串 的長度，"pwke" 是一個子序列绢片，不是子串岛琼。
解答：
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
/**
* 最基礎(chǔ)遍歷,時間復(fù)雜度：O(n ^3) 性能很差
* @param s
* @return
*/
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for(int i = 0;i < n;i ++){
for(int j = i + 1;j <= n;j ++){
if (allUnique(s,i,j)){
ans = Math.max(ans,j - i);
}
}
}
return ans;
}
public boolean allUnique(String s,int start,int end){
Set<Character> set = new HashSet<>();
for(int i = start;i < end;i ++){
Character ch = s.charAt(i);
if (set.contains(ch))return false;
set.add(ch);
}
return true;
}
/**
* 滑動窗口 會把最大的不重復(fù)字符串留住，最后留在窗口里面的不一定是最大的不重復(fù)字符串
* 空間復(fù)雜度：O(2n) = O(n)
* @param s
* @return
*/
public int lengthOfLongestSubstring2(String s) {
int n = s.length();
int ans = 0 , i = 0, j = 0;
Set set = new HashSet();
while (i < n && j< n){
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j));
j += 1;
ans = Math.max(ans,j - i);
}else{
set.remove(s.charAt(i));
i += 1;
}
}
return ans;
}
/**
* 滑動窗口優(yōu)化熙涤，Set改為Map存儲困檩，減少了查找對比的時間復(fù)雜度
* @param s
* @return
*/
public int lengthOfLongestSubstring3(String s) {
int n = s.length();
int ans = 0 , i = 0, j = 0;
/**
* 使用map減少了比對的時候的查找時間復(fù)雜度，不需要遍歷整個set悼沿，O(n),map直接O(1)查找對比
*/
Map<Character,Integer> map = new HashMap();
while (i < n && j< n){
if (!map.containsKey(s.charAt(j))){
map.put(s.charAt(j),j);
j += 1;
ans = Math.max(ans,j - i);
}else{
map.remove(s.charAt(i));
i += 1;
}
}
return ans;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.lengthOfLongestSubstring3("pwwkew"));
}
}
