2018-06-14 11:56:28 領釦網

題目描述：

給定一個字符串，找出不含有重複字符的

最長子串的長度。

示例：

給定 "abcabcbb" ，沒有重複字符的最長子串是 "abc" ，那麼長度就是 3。
給定 "bbbbb" ，最長的子串就是 "b" ，長度是 1。
給定 "pwwkew" ，最長子串是 "wke" ，長度是 3。請注意答案必須是一個子串，"pwke" 是子序列而不是子串。

方法一、暴力法：

思路

逐個檢查所有的子字符串，看它是否不含有重複的字符。

算法

假設我們有一個函數 boolean allUnique(String substring) ，如果子字符串中的字符都是唯一的，它會返回true，否則會返回 false。我們可以遍歷給定字符串 s 的所有可能的子字符串並調用函數 allUnique。如果事實證明返回值為true，那麼我們將會更新無重複字符子串的最大長度的答案。

現在讓我們填補缺少的部分：

為了枚舉給定字符串的所有子字符串，我們需要枚舉它們開始和結束的索引。假設開始和結束的索引分別為 i 和 j。那麼我們有 0 ≤ i < j ≤ n （這裡的結束索引 j 是按慣例排除的）。因此，使用 i 從 0 到 n−1 以及 j 從 i+1 到 n 這兩個嵌套的循環，我們可以枚舉出 s 的所有子字符串。
要檢查一個字符串是否有重複字符，我們可以使用集合。我們遍歷字符串中的所有字符，並將它們逐個放入 set 中。在放置一個字符之前，我們檢查該集合是否已經包含它。如果包含，我們會返回 false。循環結束後，我們返回 true。

複雜度分析

時間複雜度：O(n^3)。
要驗證索引範圍在 [i, j) 內的字符是否都是唯一的，我們需要檢查該範圍中的所有字符。因此，它將花費 O(j - i) 的時間。
對於給定的 i，對於所有 j ∈ [i+1, n] 所耗費的時間總和為：

因此，執行所有步驟耗去的時間總和為：

空間複雜度：O(min(n, m))，我們需要 O(k) 的空間來檢查子字符串中是否有重複字符，其中 k 表示 Set 的大小。而 Set 的大小取決於字符串 n 的大小以及字符集/字母 m 的大小。

方法二、滑動窗口：

算法

暴力法非常簡單。但它太慢了。那麼我們該如何優化它呢？

在暴力法中，我們會反覆檢查一個子字符串是否含有有重複的字符，但這是沒有必要的。如果從索引 i 到 j−1 之間的子字符串 sij 已經被檢查為沒有重複字符。我們只需要檢查 s[j] 對應的字符是否已經存在於子字符串 sij 中。

要檢查一個字符是否已經在子字符串中，我們可以檢查整個子字符串，這將產生一個複雜度為 O(n^2) 的算法，但我們可以做得更好。

通過使用 HashSet 作為滑動窗口，我們可以用 O(1) 的時間來完成對字符是否在當前的子字符串中的檢查。

滑動窗口是數組/字符串問題中常用的抽象概念。窗口通常是在數組/字符串中由開始和結束索引定義的一系列元素的集合，即 [i, j)（左閉，右開）。而滑動窗口是可以將兩個邊界向某一方向“滑動”的窗口。例如，我們將 [i, j) 向右滑動 11 個元素，則它將變為 [i+1, j+1)（左閉，右開）。

回到我們的問題，我們使用 HashSet 將字符存儲在當前窗口 [i, j)（最初 j = i）中。然後我們向右側滑動索引 j，如果它不在 HashSet 中，我們會繼續滑動 j。直到 s[j] 已經存在於 HashSet 中。此時，我們找到的沒有重複字符的最長子字符串將會以索引 i 開頭。如果我們對所有的 i 這樣做，就可以得到答案。