前言
LeetCode第3題，“無重複字元的最長子串”，曾經面試的過程中遇到過的一道演算法題。透過這道題，我們能夠學到演算法中一個比較常見的解題方法：滑動視窗演算法。
由於LeetCode中很多題都是基於“滑動視窗演算法”進行解答，因此本篇文章將重點放在“滑動視窗”上，而不僅僅是這道演算法題。當理解了滑動視窗的基本原理之後，所有類似的題都可以輕易解答。
下面來看具體的題目和解題方法。
“無重複字元的最長子串”題目連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
題目描述：
給定一個字串，請你找出其中不含有重複字元的 最長子串 的長度。
示例：
輸入: s = "abcabcbb"輸出: 3 解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。題目很簡單，就是從一個字串中找出不包含重複字元的最長子串的長度。
該題如果用暴利破解的方法進行迴圈判斷，則時間複雜度直接變為O(n^2)，是比較恐怖的。因此，可採取滑動視窗的方法來降低時間複雜度。
什麼是滑動視窗？滑動視窗演算法是在一個特定大小的字串或陣列上進行操作，而不在整個字串和陣列上操作，這就降低了問題的複雜度，從而也降低了迴圈的巢狀深度。滑動視窗主要應用在陣列和字串的場景。
簡單示例先透過一個簡單的示例來看一下滑動視窗的運作，比如有一個數組[1,3,5,6,2,2]，設定滑動視窗（window）大小為3，那麼當視窗從陣列開始位置滑動到最終位置時依次計算每個視窗內3個元素的和，表示為sum。
上圖我們可以看出，隨著視窗在陣列上向右移動，視窗內的資料也在不斷變化，我們只用對視窗內連續區間內的資料進行處理即可。由於區間是連續的，因此當視窗移動時只用對舊視窗的資料進行裁剪處理，這樣便減少了重複計算，降低了時間複雜度。
以上圖為例，當視窗位於[1,3,5]時，處理完該視窗的資料之後，將視窗向右移動一格，等於是將原有視窗左邊的1裁剪掉，然後將視窗右邊的6新增上，而整個過程看起來就像視窗在向右移動一樣。
對於類似“請找到滿足 xx 的最 x 的區間（子串、子陣列）的 xx ”這類問題都可以使用該方法進行解決。
滑動視窗的基本步驟需要注意的是：視窗的移動是按照移動的順序來進行的；視窗的大小不一定是固定的，可以不斷縮小或變大的。
對於滑動視窗演算法的基本解題思路，以字串S示例如下：
（1）採用雙指標來指定視窗的範圍，初始化left=right=0，而索引閉區間[left,right]便是一個視窗。（2）不斷增大視窗的right指標，直到視窗中的字串滿足條件。（3）此時，停止right的增加，轉而不斷增加left指標，用於縮小視窗[left,right]，直到視窗中的字串不再符合要求。每增加一次left，需要更新一輪結果。（4）重複第2和第3步，直到right到達字串的盡頭。其中，第2步相當於在尋找一個「可行解」，然後第3步在最佳化這個「可行解」，最終找到最優解。左右指標輪流前進，視窗大小增增減減，視窗不斷向右滑動。
解題學習了視窗滑動之後，我們回到LeetCode的題目上，是將上述示例的固定視窗變為了變化大小的視窗，而將求和換成了判斷是否包含指定字元。
因此，套用上面的思路來進行分析。以字串“dvdf”為例，透過下圖來演示滑動的過程。
在上述流程中，可分解為以下步驟：
（1）選定初始值left=right=0，也就是視窗[0,0]。（2）判斷right右邊字元在視窗內是否已經存在；（3）發現字元v在視窗中沒有，則可right右移一位，視窗變為[0,1]；（4）繼續擴充套件右邊界，right=2，發現d已經存在於視窗當中，則停止繼續右移；（5）此時視窗的長度便是以d開通的子串的長度，比較當前視窗長度和歷史max（預設值0）大小，發現2>0，於是更新max為2。（6）開始移動left，視窗變為[1,1]；（7）繼續擴充套件右邊界，發現d不存在於視窗當中，此時視窗變為[1,2]；（8）繼續擴充套件右邊界，發現f不存在於視窗當中，此時視窗變為[1,3]；（9）到達字串的最大長度，停止右移，此時比較當前視窗長度和歷史max大小，發現3>2，於是更新max為3。（10）得出，不包含重複字元的最長子串的長度3。理解了上述步驟，我們再來看原題的Java程式碼實現：
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int k = 0, max = 0; Set<Character> set = new HashSet<>(); for(int i=0; i< n; i++){ if(i != 0){ set.remove(s.charAt(i-1)); } while(k < n && !set.contains(s.charAt(k))){ set.add(s.charAt(k)); k++; } max = Math.max(max,set.size()); } return max; }}上述程式碼中for迴圈中的i相當於left，k相當於right，而max是儲存歷史最長字串的值。而視窗內的字元透過Set<Character>來儲存，判重透過Set的contains方法，獲取最大值透過Math的max方法來操作。
最後，此演算法的時間複雜度為O(n)，其中n是字串的長度。左指標和右指標分別會遍歷整個字串一次。
小結本篇文章我們重點學習的應該是滑動視窗的原理及步驟，當掌握了滑動視窗的知識之後，LeetCode的題只不過是對滑動視窗的一個示例而已。對於演算法題，千萬不要死記硬背解題程式碼。