【圖解】三種解法不斷優化帶你手撕 LeetCode第三號題：無重複字元的最長子串
- 2019 年 12 月 19 日
- 筆記
來源於公眾號：苦逼的碼農
作者：stul
刷題，AC 不是最終目的，而應該力求最優解，並且總結歸納每個解法的精髓
題目描述
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
示例1： 輸入: "abcabcbb"輸出: 3 解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。 示例2： 輸入: "pwwkew" 輸出: 3 解釋: 因為無重複字元的最長子串是 "wke"，所以其長度為 3。 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
思路與解法
思路1：暴力法，實際解題中不會使用暴力法，這並不代表我們可以忽略它。
索引從字元串的第一位開始，將後面的字元依次加入到 set 裡面。如果 set 裡面已經有了該字元，此次循環結束，內循環結束後記錄 size。字元串的每一位都用這種方法去計算，得到的最大的 size 即是答案。
程式碼如下（不是Java的也看得懂，我進行了關鍵語法的注釋，下同）
public int lengthOfLongestSubstring(String s) { int maxLen = 0; for(int i = 0; i < s.length(); i++){ // 創建一個存放字元的集合 HashSet<Character> set = new HashSet<>(); for(int j = i; j < s.length(); j++) { // 判斷集合是否存在第 j 個字元 if(set.contains(s.charAt(j))) break; set.add(s.charAt(j)); } maxLen = Math.max(maxLen,set.size()); } return maxLen; } （為方便閱讀，給出截圖）
時間複雜度：O()
空間複雜度：O(m) ，m 為無重複字元的最長子串的長度。
由 思路1 的圖可知，i 每次都從下一位開始，其實做了很多無效的計算。思路2將其優化。
思路2：我們設置兩根指針（i 和 j ）與一個集合set。兩個指針之間是一個範圍，我們要維護這個範圍內不能出現重複的字元。而這個 set 就是是用來判斷範圍內是否有重複的字元。具體做法如下：i 和 j 開始的時候都指向 字元串首。然後執行下面兩個步驟。
- 如果 j 指針所指元素未在 set 裡面，我們將其 add 進 set 。繼續後移 j 。
- 如果 j 指針所指元素在 set 裡面，我們將 i 指針所指元素從 set 中移除，繼續後移 i 。i 會一直往後移，直到 j 的元素不在 set 裡面。
我們那示例 2 來詳細理解一下。
這個過程中，i 與 j 的範圍最大的時候，就是我們要求的答案。
HashSet<Character> set = new HashSet<>(); int i = 0, j = 0, maxLen = 0; while (i < s.length() && j < s.length()){ if (!set.contains(s.charAt(j))){ set.add(s.charAt(j)); j++; maxLen = Math.max(maxLen,j - i); }else { set.remove(s.charAt(i)); i++; } } return maxLen; 程式碼圖片
時間複雜度：O(2n) = O(n) ， i 和 j 兩個指針。
空間複雜度：O(m) ，m 為無重複字元的最長子串的長度。
思路2 中，我們在遇到重複的字元時，不斷在移動 i 指針。這個地方其實可以優化，讓 i 指針直接跳到重複元素的下一個位置。
思路3: 讓 i 指針直接跳到重複元素的下一個位置。那我們就需要保存每個元素以及它的位置。一個 Value, 一個 Index 。自然會想到 HashMap 。
我們繼續拿示例 2 來演示一下。
這個地方，能看到優化，但是並不明顯。測試用例：pabcwwkew，在紙上用思路 2 和思路 3 畫一下這個過程，你會發現思路 3 比思路 2 省略了很多步驟。
public static int lengthOfLongestSubString4(String s){ // 創建一個 key-value 為 字元-下標 相映射的哈希表 HashMap<Character,Integer> map = new HashMap<>(); int left = 0, maxLen = 0; for(int i = 0; i < s.length(); i++){ // 判斷是否存在該key if(map.containsKey(s.charAt(i))){ left = Math.max(map.get(s.charAt(i)) + 1,left); } maxLen = Math.max(maxLen, i - left + 1); map.put(s.charAt(i),i); } return maxLen; } 程式碼圖片
時間複雜度: O(n) ， 最優解。空間複雜度: O(m) ，m 為無重複字元的最長子串的長度。
在上面所提到的 「範圍」，就是一個滑動窗口。
其他 leetcode 題目
- 【leetcode】16. 最接近的三數之和
- 【leetcode】15：三數之和
- 【leetcode】14：最長公共前綴
- 【leetcode】13：羅馬數字轉整數
- 【leetcode】12：整數轉羅馬數字
- 【leetcode】11. Container With Most Water | 盛最多水的容器
推薦閱讀全部文章詳細分類與整理（演算法+數據結構+電腦基礎） 寫了很久，這是一份適合普通大眾/科班/非科班的『學習路線』有必要說一說即將到來的春招（經歷+重要性+如何準備） 普普通通，我的三年大學歷經兩個月，我的秋招之路結束了！
