歡迎來到啾啾的博客🐱。
記錄學習點滴。分享工作思考和實用技巧，偶爾也分享一些雜談💬。
有很多很多不足的地方，歡迎評論交流，感謝您的閱讀和評論😄。
目錄
- 引言
- 1 雙指針：Two Pointers
- 1.1 左右指針
- 1.2 滑動窗口
引言
在刷完代碼隨想錄、了解了基本的數據結構后，讓我們學算法（時隔四個月了）。
閱讀本篇可對基礎的雙指針算法有深入理解。
簡單來說，解決算法問題我們可以遵循一些簡單的模板，確認步驟、找合適的數據結構，解。
1 雙指針：Two Pointers
- 什么是“雙指針”模式？它主要想解決什么問題？
雙指針核心是減少遍歷，優化時間復雜度。
主要是為了將暴力解法中 O(n2) 的時間復雜度（兩層循環）優化到 O(n)（一層循環）。它本身就是一種 O(n) 的解法。
- “左右指針”和“快慢指針”這兩種方法，在使用場景上最大的區別是什么？（比如，一個通常用在什么數據結構上，另一個用在什么上？一個對原始數據有什么要求？）
左右指針主要適用于有序數組(不是非要有序數組)，適用于搜索精確值。
快慢指針核心在于利用速度差來解決問題，用來解決數據結構中位置和環路的問題。
最經典的應用場景是鏈表，而不是數組。
1.1 左右指針
左右指針主要使用與有序數組，也通用于數組。
因為左右指針的條件判斷對于位置信息有要求，需要有效移動位置。
LeetCode:
125. 驗證回文串
簡單的回文字符串判斷。利用雙指針快速遍歷，優化時間復雜度。
11. 盛最多水的容器
明白移動短板是收益最高的選項后，利用雙指針移動短板。
這里除了雙指正還需要注意的是，我們寫解答時，要盡量分開狀態處理和狀態轉移。
- 錯誤示例
class Solution {/**移動短板，因為短板沒有潛力了*/public int maxArea(int[] height) {int length = height.length;int left = 0;int right =length-1;int currentArea = Math.min(height[left],height[right]) * ( right-left);;while(left < right){if(height[left] < height[right]){left ++;}else{right --;}int tempArea = Math.min(height[left],height[right]) * ( right-left);currentArea = tempArea > currentArea? tempArea:currentArea;}return currentArea;}
}
- 正確示例
class Solution {public int maxArea(int[] height) {int maxArea = 0;int left = 0;int right = height.length - 1;while (left < right) {// 1. 先用當前的 left 和 right 計算面積int currentWidth = right - left;int currentHeight = Math.min(height[left], height[right]);int currentArea = currentWidth * currentHeight;// 2. 更新歷史最大面積maxArea = Math.max(maxArea, currentArea);// 3. 然后再根據短板移動指針，為下一次循環做準備if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}
這樣修改后，循環體內部的邏輯非常純粹：對于當前的?left?和?right?狀態，我們先計算它的面積并更新?maxArea，然后再決定下一步怎么走。每一步都處理一個獨立的狀態，非常清晰。
1.2 滑動窗口
滑動窗口模式，顧名思義，就像有一個大小可變的“窗口”在一個序列（通常是數組或字符串）上滑動。它也是用兩個指針來定義的，通常我們叫它們?left?和?right，但這里的?left?和?right?都從起點開始，共同構成一個窗口?[left, right)?或?[left, right]。
這個模式專門用來解決“連續子數組”或“連續子字符串”的相關問題，例如：
- 找到滿足某條件的最長/最短的連續子串。
- 找到所有滿足某條件的連續子數組的數量。
和左右指針定初始位置、判斷條件往相反的方向走不同。
滑動窗口是兩個指針相同一個方向移動：
- 窗口擴大：?不斷移動?right?指針，讓新的元素進入窗口。
- 更新狀態：?每當新元素進入，就更新窗口內的信息（例如：窗口內元素的和、不同字符的數量等）。
- 判斷收縮：?當窗口內的狀態不再滿足題目要求時（或者說，滿足了收縮條件時），就需要移動?left?指針，將元素移出窗口，這個過程叫作窗口收縮。
- 持續收縮：?持續移動?left?指針，直到窗口內的狀態再次滿足題目要求。
- 重復以上過程，直到?right?指針到達序列末尾。
3. 無重復字符的最長子串
import java.util.HashSet;
import java.util.Set;class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length();if (n == 0) {return 0;}// 1. 初始化Set<Character> charSet = new HashSet<>();int maxLen = 0;int left = 0; // 窗口左邊界int right = 0; // 窗口右邊界// 2. 循環，讓 right 指針作為主導，探索整個字符串while (right < n) {// 3. 嘗試擴大窗口：檢查 right 指向的字符是否已在窗口中char charToadd = s.charAt(right);// 4. 如果有重復，觸發窗口收縮// 注意這里是 while 循環，因為可能需要收縮多次while (charSet.contains(charToadd)) {// 從 Set 中移除 left 指向的字符charSet.remove(s.charAt(left));// 收縮窗口left++;}// 5. 此時窗口內一定沒有重復了，可以安全地加入新字符charSet.add(charToadd);// 6. 更新最大長度// 每一次擴大窗口后，都計算一下當前長度，并嘗試更新最大值maxLen = Math.max(maxLen, right - left + 1);// 7. 真正地擴大窗口，為下一次循環做準備right++;}return maxLen;}
}
還有209. 長度最小的子數組。
拓展：leetcode題解與題目匯總：powcai滑動窗口題解
)
