1.題目描述
給定一個(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è)子序列，不是子串典格。
2.思路分析與解答
首先最直接的方法肯定是暴力匹配岛宦，類似于冒泡排序的遍歷方式，不斷的選出子串耍缴，然后進(jìn)行判斷子串是否有重復(fù)數(shù)字砾肺。（這肯定不可取）
方法二（滑動(dòng)窗口法）：
與之前求兩個(gè)數(shù)字之和類似防嗡，我們利用集合的屬性來減少判斷变汪，HashSet是一種可行的方案。
窗口通常是在數(shù)組/字符串中由開始和結(jié)束索引定義的一系列元素的集合本鸣，即 [i, j)（左閉疫衩，右開）。而滑動(dòng)窗口是可以將兩個(gè)邊界向某一方向“滑動(dòng)”的窗口。例如闷煤，我們將 [i, j) 向右滑動(dòng)1個(gè)元素童芹，則它將變?yōu)?[i+1, j+1)（左閉，右開）鲤拿。
使用 HashSet 將字符存儲在當(dāng)前窗口 [i, j)[i,j)（最初 j = i=0）中假褪。 然后我們向右側(cè)滑動(dòng)索引 j，如果它不在 HashSet 中近顷，我們會繼續(xù)滑動(dòng) j生音。直到 s[j] 已經(jīng)存在于 HashSet 中。此時(shí)窒升，我們找到的沒有重復(fù)字符的最長子字符串將會以索引 i 開頭缀遍。如果我們對所有的 i 這樣做，就可以得到答案饱须。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// 如果沒有重復(fù)域醇，j繼續(xù)右移
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
//有重復(fù)，則首位置右移i++蓉媳，直到i與j對應(yīng)的元素相同
set.remove(s.charAt(i++));
}
}
return ans;
}
}
方法三（優(yōu)化滑動(dòng)窗口）：
//有重復(fù)譬挚，則首位置右移i++，直到i與j對應(yīng)的元素相同
這里其實(shí)是有無用操作的酪呻，如果我們能夠存儲前一個(gè)重復(fù)字符的坐標(biāo)减宣，則可以省去
這里我們想起了HashMap來存儲
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length(),ans=0,left=0;
Map<Character,Integer> map=new HashMap<>();
for(int j=0;j<n;j++){
if(map.containsKey(s.charAt(j))){
//這里要保證，left不能左移玩荠，只能右移漆腌，即上面的i++
left=Math.max(left,map.get(s.charAt(j))+1);
}
map.put(s.charAt(j), j);
ans=Math.max(ans, j-left+1);
}
return ans;
}
}
