• 關于每個知識點的例題

• 可以自己看力扣標準題解。也可以在嗶哩嗶哩上看。
• 想看我的，就到github 看 - 庫 ，介紹里寫的算法講解那些，里面有知識點，有題庫。題庫，每天都發題，可能跟博客的進度不一樣。因為我上傳和整理以及做題需要時間，大家可以私發信息給我，我會盡量提前整理你們要的東西。
• 這個是github鏈接，找 - 庫，看里面的題庫對應知識點部分，就能找到題
• 題庫里肯定不會只有這幾道雙指針題，只要我做到一道，就會交一道。這些只是為了理解知識點而用的。
• 覺得不錯的話，麻煩點個贊給github。謝謝。

一、了解雙指針

雙指針（Two Pointers）是一種常用的算法技巧，通常用于解決數組或鏈表中的問題。它的核心思想是使用兩個指針（或索引）在數據結構中遍歷或搜索，從而高效地解決問題。雙指針技巧通常可以將時間復雜度從 (O(n^2)) 優化到 (O(n))。

推薦先看這個視頻，再看下面文章

---

二、 雙指針的常見應用場景

1. 有序數組的兩數之和：

   • 給定一個有序數組和一個目標值，找到兩個數使它們的和等于目標值。
   • 使用雙指針，一個指向數組開頭，一個指向數組末尾，根據和的大小移動指針。

2. 移除數組中的重復元素：

   • 給定一個有序數組，原地移除重復元素。
   • 使用雙指針，一個指針用于遍歷數組，另一個指針用于記錄非重復元素的位置。

3. 滑動窗口問題：

   • 給定一個數組和一個窗口大小，找到滿足條件的子數組。
   • 使用雙指針表示窗口的左右邊界，根據條件滑動窗口。

4. 鏈表的快慢指針：

   • 判斷鏈表是否有環，或找到鏈表的中間節點。
   • 使用快慢指針，快指針每次移動兩步，慢指針每次移動一步。

---

二、 雙指針的技巧總結

1. 對撞指針：

對撞指針 是一種常用的雙指針技巧，通常用于解決數組或字符串中的問題。它的核心思想是使用兩個指針，一個從數組的起始位置（左指針）開始，另一個從數組的末尾位置（右指針）開始，通過向中間移動來解決問題。

---

1.1、對撞指針的核心思想

1. 指針的初始化：

   • 左指針 l 指向數組的起始位置（l = 0）。
   • 右指針 r 指向數組的末尾位置（r = nums.size() - 1）。

2. 指針的移動規則：

   • 根據問題的要求，決定左指針或右指針的移動方向。
   • 通常，左指針向右移動，右指針向左移動。

3. 終止條件：

   • 當左指針和右指針相遇或交叉時，算法結束。

---

1.2、對撞指針的總結

1. 適用場景：

   • 有序數組中的兩數之和、三數之和。
   • 反轉數組或字符串。
   • 驗證回文串。
   • 盛最多水的容器。

2. 核心思想：

   • 使用兩個指針從數組的兩端向中間移動，通過比較指針指向的元素來解決問題。

3. 時間復雜度：

   • 通常為 (O(n))，因為每個元素最多被訪問一次。

4. 空間復雜度：

   • 通常為 (O(1))，只使用了常數級別的額外空間。

---

2. 快慢指針：

快慢指針 是一種常用的雙指針技巧，通常用于解決鏈表或數組中的問題。它的核心思想是使用兩個指針，一個移動速度快（快指針），一個移動速度慢（慢指針），通過它們的相對移動來解決問題。

---

2.1、快慢指針的核心思想

1. 快指針和慢指針的移動速度：

   • 快指針每次移動兩步。
   • 慢指針每次移動一步。

2. 相對速度：

   • 快指針和慢指針的相對速度是 1，即快指針每次比慢指針多走一步。

3. 終止條件：

   • 當快指針到達鏈表末尾（或數組末尾）時，慢指針通常指向目標位置。

---

2.2、快慢指針的總結

1. 適用場景：

   • 鏈表中的環檢測、中間節點查找。
   • 數組中的重復元素刪除、重復數查找。

2. 核心思想：

   • 快指針和慢指針以不同的速度移動，通過相對速度解決問題。

3. 時間復雜度：

   • 通常為 (O(n))，因為每個元素最多被訪問兩次。

4. 空間復雜度：

   • 通常為 (O(1))，只使用了常數級別的額外空間。

---

3. 滑動窗口：

3.1、滑動窗口的兩種情況

3.1.1、情況1：固定大小的窗口

• 特點：
  • 窗口的大小是固定的。
  • 通常用于解決需要在固定長度的子數組或子串中查找滿足條件的問題。
• 示例問題：
  • 在一個數組中，找到長度為 k 的連續子數組，使得子數組的和大于 target。
• 解決方法：
  • 初始化左指針 l = 0，右指針 r = k - 1。
  • 計算窗口內的和，如果滿足條件，返回結果。
  • 如果不滿足條件，移動窗口：l++，r++，繼續檢查新的窗口。

3.1.2、情況2：可變大小的窗口

• 特點：
  • 窗口的大小不固定。
  • 通常用于解決需要在不定長度的子數組或子串中查找滿足條件的問題。
• 示例問題：
  • 在一個數組中，找到和大于等于 target 的最短連續子數組。
• 解決方法：
  • 初始化左指針 l = 0，右指針 r = 0。
  • 右指針 r 向右移動，擴大窗口，直到窗口內的和滿足條件。
  • 左指針 l 向右移動，縮小窗口，嘗試找到更短的滿足條件的子數組。

3.4、滑動窗口的核心思想

1. 窗口的定義：

   • 窗口是數組或字符串中的一個連續子區間，由左指針 l 和右指針 r 定義。

2. 窗口的移動：

   • 擴大窗口：右指針 r 向右移動，增加窗口的大小。
   • 縮小窗口：左指針 l 向右移動，減少窗口的大小。

3. 條件的判斷：

   • 在窗口移動的過程中，根據問題的要求判斷當前窗口是否滿足條件。

4. 分離指針：

分離指針 是一種雙指針技巧，通常用于解決涉及多個數組或鏈表的問題。它的核心思想是使用兩個指針分別遍歷不同的數組或鏈表，通過它們的相對移動來解決問題。

---

4.1、分離指針的常見應用場景

1. 合并兩個有序數組或鏈表：

   • 將兩個有序數組合并為一個有序數組。
   • 將兩個有序鏈表合并為一個有序鏈表。

2. 查找兩個數組的交集：

   • 找到兩個有序數組的交集。

3. 判斷一個數組是否是另一個數組的子序列：

   • 判斷一個數組是否是另一個數組的子序列。

4. 滑動窗口問題：

   • 使用兩個指針分別表示窗口的左右邊界。

---

4.2、分離指針的核心思想

1. 指針的初始化：

   • 每個指針分別指向一個數組或鏈表的起始位置。

2. 指針的移動規則：

   • 根據問題的要求，決定每個指針的移動方向。
   • 通常，指針的移動方向是單向的（從左到右）。

3. 終止條件：

   • 當某個指針到達數組或鏈表的末尾時，算法結束。

---

4.3、分離指針的總結

1. 適用場景：

   • 合并兩個有序數組或鏈表。
   • 查找兩個數組的交集。
   • 判斷一個數組是否是另一個數組的子序列。

2. 核心思想：

   • 使用兩個指針分別遍歷不同的數組或鏈表，通過比較指針指向的元素來解決問題。

3. 時間復雜度：

   • 通常為 (O(m + n))，其中 (m) 和 (n) 是兩個數組或鏈表的長度。

4. 空間復雜度：

   • 通常為 (O(1))，只使用了常數級別的額外空間。

---

三、 雙指針的時間復雜度

• 雙指針通常可以將時間復雜度從 (O(n^2)) 優化到 (O(n))，因為每個指針最多遍歷數組或鏈表一次。

---

四、例題

• 對撞指針
  力扣hot100兩數之和
• 快慢指針
  力扣hot100移動零
• 滑動窗口
  力扣LCR長度最小的子數組
• 分離指針
  力扣21、合并2個有序鏈表