一、題目
給定一個(gè)字符串舍扰，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度具垫。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"趟卸，所以其長(zhǎng)度為 3贮庞。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"峦筒，所以其長(zhǎng)度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"窗慎，所以其長(zhǎng)度為 3物喷。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列脯丝，不是子串。
二伏伐、解答
2.1 方法一：暴力法
假設(shè)我們有一個(gè)函數(shù) boolean allUnique(String substring) 宠进，如果子字符串中的字符都是唯一的，它會(huì)返回 true藐翎，否則會(huì)返回 false材蹬。 我們可以遍歷給定字符串 s 的所有可能的子字符串并調(diào)用函數(shù) allUnique。 如果事實(shí)證明返回值為 true吝镣，那么我們將會(huì)更新無(wú)重復(fù)字符子串的最大長(zhǎng)度的答案堤器。
現(xiàn)在讓我們填補(bǔ)缺少的部分：
為了枚舉給定字符串的所有子字符串，我們需要枚舉它們開始和結(jié)束的索引末贾。假設(shè)開始和結(jié)束的索引分別為 ii 和 jj闸溃。那么我們有 0 <= i <j <=n（這里的結(jié)束索引 j是按慣例排除的）。因此拱撵，使用 i從 0 到 n - 1 以及 j 從 i+1到 n 這兩個(gè)嵌套的循環(huán)辉川，我們可以枚舉出 s 的所有子字符串。
要檢查一個(gè)字符串是否有重復(fù)字符拴测，我們可以使用集合乓旗。我們遍歷字符串中的所有字符，并將它們逐個(gè)放入 set 中集索。在放置一個(gè)字符之前屿愚，我們檢查該集合是否已經(jīng)包含它。如果包含务荆，我們會(huì)返回 false妆距。循環(huán)結(jié)束后，我們返回 true函匕。
public class Solution {
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;
}
}
時(shí)間復(fù)雜度：O(n^3)毅厚。
2.2 方法二：滑動(dòng)窗口
暴力法非常簡(jiǎn)單，但它太慢了浦箱。那么我們?cè)撊绾蝺?yōu)化它呢吸耿？
在暴力法中，我們會(huì)反復(fù)檢查一個(gè)子字符串是否含有有重復(fù)的字符酷窥，但這是沒(méi)有必要的咽安。如果從索引 i 到 j - 1 之間的子字符串 sij已經(jīng)被檢查為沒(méi)有重復(fù)字符。我們只需要檢查 s[j] 對(duì)應(yīng)的字符是否已經(jīng)存在于子字符串 sij中蓬推。
要檢查一個(gè)字符是否已經(jīng)在子字符串中妆棒，我們可以檢查整個(gè)子字符串，這將產(chǎn)生一個(gè)復(fù)雜度為 O(n^2)的算法，但我們可以做得更好糕珊。
通過(guò)使用 HashSet 作為滑動(dòng)窗口动分，我們可以用 O(1) 的時(shí)間來(lái)完成對(duì)字符是否在當(dāng)前的子字符串中的檢查。
滑動(dòng)窗口是數(shù)組/字符串問(wèn)題中常用的抽象概念红选。 窗口通常是在數(shù)組/字符串中由開始和結(jié)束索引定義的一系列元素的集合澜公，即 [i, j)（左閉，右開）喇肋。而滑動(dòng)窗口是可以將兩個(gè)邊界向某一方向“滑動(dòng)”的窗口坟乾。例如，我們將 [i, j) 向右滑動(dòng) 1 個(gè)元素蝶防，則它將變?yōu)?[i+1, j+1)（左閉甚侣，右開）。
回到我們的問(wèn)題间学，我們使用 HashSet 將字符存儲(chǔ)在當(dāng)前窗口 [i, j)（最初 j = i）中殷费。 然后我們向右側(cè)滑動(dòng)索引 j，如果它不在 HashSet 中低葫，我們會(huì)繼續(xù)滑動(dòng) j宗兼。直到 s[j] 已經(jīng)存在于 HashSet 中。此時(shí)氮采，我們找到的沒(méi)有重復(fù)字符的最長(zhǎng)子字符串將會(huì)以索引 i 開頭殷绍。如果我們對(duì)所有的 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) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
時(shí)間復(fù)雜度：O(2n) = O(n)主到，在最糟糕的情況下，每個(gè)字符將被 i 和 j 訪問(wèn)兩次躯概。
2.3 方法三：優(yōu)化滑動(dòng)窗口
public int lengthOfLongestSubstring(String s) {
int n = s.length(), maxLength = 0;
int index = 0;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(s.charAt(i))) {
index = Math.max(map.get(s.charAt(i)) + 1, index);
}
maxLength = Math.max(maxLength, i - index + 1);
map.put(s.charAt(i), i);
}
return maxLength;
}
