1 雙指針基礎(chǔ)知識

1.1 雙指針簡介

雙指針（Two Pointers） 是一種常用的算法技巧，通常用于在數(shù)組或鏈表中進行遍歷或搜索。它使用兩個指針在不同的位置上移動，以解決特定的問題。

雙指針常見的應(yīng)用場景包括：

1. 快慢指針：兩個指針方向相同，但是使用兩個指針以不同的速度遍歷鏈表，用于解決鏈表中的環(huán)檢測、鏈表中點、鏈表倒數(shù)第k個節(jié)點等問題。
2. 左右指針（對撞指針）：在有序數(shù)組中，使用兩個指針從數(shù)組的兩端向中間移動，以解決查找目標值、兩數(shù)之和、三數(shù)之和等問題。
3. 分離雙指針：兩個指針分別屬于不同的數(shù)組/鏈表。

雙指針算法通常具有較低的時間復(fù)雜度，并且可以在一次遍歷中完成任務(wù)，因此在很多問題中都有很好的應(yīng)用。

1.2 左右指針（對撞指針）

左右指針（Left and Right Pointers）是雙指針算法中的一種常見技巧。它通常用于在有序數(shù)組或字符串中查找目標值、尋找滿足某種條件的子序列等問題。

左右指針的基本思想是，使用兩個指針分別指向數(shù)組或字符串的左右兩端，然后根據(jù)問題的要求，通過移動指針的位置來逼近或搜索目標。

基本步驟

1. 兩個指針 $left$ 和 $right$。 $left$ 指向序列第一個元素（ $left=0$ ），$right$ 指向序列最后一個元素（ $right=len(nums)?1$ ）。
2. 循環(huán)體中將左右指針相向移動，當(dāng)滿足一定條件時，將左指針右移（$left+=1$ ）。當(dāng)滿足另外一定條件時，將右指針左移（$right+=1$ ）。
3. 直到兩個指針相撞（$left=right$ ），或者滿足其他要求的特殊條件時，跳出循環(huán)體。

偽代碼模板

left, right = 0, len(nums) - 1while left < right:if 滿足要求的特殊條件:return 符合條件的值 elif 一定條件 1:left += 1elif 一定條件 2:right -= 1return 沒找到 或 找到對應(yīng)值

適用范圍

1. 有序數(shù)組或有序鏈表：左右指針可以在有序數(shù)組或有序鏈表中進行查找、搜索、比較等操作。通過左右指針的移動，可以快速定位目標值或滿足特定條件的元素。

2. 滑動窗口問題：滑動窗口問題通常涉及在數(shù)組或字符串上定義一個窗口，并通過移動窗口的左右邊界來解決問題。左右指針可以用于表示窗口的左右邊界，并根據(jù)問題的要求進行移動和調(diào)整。

3. 兩數(shù)之和、三數(shù)之和等問題：在有序數(shù)組中查找滿足特定條件的數(shù)對或數(shù)組合時，左右指針可以進行逼近，快速找到滿足條件的解。

4. 回文字符串判斷：左右指針可以用于判斷字符串是否是回文字符串。通過左右指針從兩端向中間移動，并比較對應(yīng)位置的字符是否相等，可以判斷字符串是否是回文。

1.3 快慢指針

快慢指針（Fast and Slow Pointers）基本思想是使用兩個指針，一個指針（快指針 fast）移動速度較快，另一個指針（慢指針 slow）移動速度較慢。通過兩個指針的相對移動，可以得到一些有用的信息，從而解決問題。

基本步驟

1. 初始化快慢指針：將快指針和慢指針都指向鏈表的頭節(jié)點或數(shù)組的起始位置。$slow=0,fast=1或0$

2. 移動指針：根據(jù)問題的要求，通過移動快慢指針來逼近目標或獲取有用的信息。

   • 快指針移動：通常每次移動兩步或一步，可以快速遍歷整個鏈表或數(shù)組。$fast+=1$
   • 慢指針移動：通常每次移動一步，慢指針的移動速度較慢。$slow+=1$

3. 判斷終止條件：根據(jù)問題的要求，判斷是否滿足終止條件。

   • 例如，在鏈表中環(huán)檢測問題中，如果快指針和慢指針相遇，則存在環(huán)；如果快指針到達鏈表末尾，則不存在環(huán)。

4. 根據(jù)問題的要求返回結(jié)果。

   • 例如，在鏈表中找到中間節(jié)點的問題中，當(dāng)快指針到達鏈表末尾時，慢指針所指的節(jié)點就是中間節(jié)點。

偽代碼模板

slow = 0
fast = 1
while 沒有遍歷完：if 滿足要求的特殊條件:slow += 1fast += 1
return 合適的值

適用范圍

1. 鏈表中的環(huán)檢測：快慢指針可以用于判斷鏈表中是否存在環(huán)。快指針每次移動兩步，慢指針每次移動一步，如果鏈表中存在環(huán)，則快指針最終會追上慢指針，二者相遇。

2. 鏈表中點的查找：快慢指針可以用于找到鏈表的中間節(jié)點?？熘羔樏看我苿觾刹?#xff0c;慢指針每次移動一步，當(dāng)快指針到達鏈表末尾時，慢指針正好在鏈表的中間位置。

3. 鏈表倒數(shù)第k個節(jié)點的查找：快慢指針可以用于定位鏈表的倒數(shù)第k個節(jié)點?？熘羔樝纫苿觡個位置，然后快慢指針同時向前移動，當(dāng)快指針到達鏈表末尾時，慢指針所指的節(jié)點就是倒數(shù)第k個節(jié)點。

4. 判斷鏈表是否有交點：快慢指針可以用于判斷兩個鏈表是否相交。分別使用快慢指針遍歷兩個鏈表，如果兩個鏈表相交，則快指針和慢指針最終會相遇。

5. 數(shù)組中的重復(fù)元素查找：快慢指針可以用于在數(shù)組中查找重復(fù)元素。通過快慢指針的移動，可以找到數(shù)組中的重復(fù)元素或判斷數(shù)組是否存在重復(fù)元素。

1.4 分離雙指針

分離雙指針（Two Pointers with Separation）是一種雙指針算法的變體，它通常用于解決數(shù)組或鏈表中需要分離的問題，例如將奇偶數(shù)分離、將0和非0元素分離等。分離雙指針的基本思想是使用兩個指針，一個指針（分離指針）用于分離元素，另一個指針（遍歷指針）用于遍歷數(shù)組或鏈表。通過移動遍歷指針，并根據(jù)特定條件將元素交換到分離指針的位置，實現(xiàn)元素的分離。

基本步驟

1. 兩個指針 $lef{t}_1$、$lef{t}_2$ 。 $lef{t}_1$ 指向第一個數(shù)組的第一個元素（ $lef{t}_1=0$）， $lef{t}_2$ 指向第二個數(shù)組的第一個元素（ $lef{t}_2=0$）。

2. 當(dāng)滿足一定條件時

   1. 兩個指針同時右移，。

   2. $lef{t}_1$ 右移，$lef{t}_1+=1$。

   3. $lef{t}_2$ 右移，$lef{t}_2+=1$。

3. 當(dāng)其中一個數(shù)組遍歷完時或者滿足其他特殊條件時跳出循環(huán)體。

偽代碼模板

left_1 = 0
left_2 = 0while left_1 < len(nums1) and left_2 < len(nums2):if 一定條件 1:left_1 += 1left_2 += 1elif 一定條件 2:left_1 += 1elif 一定條件 3:left_2 += 1

適用范圍

分離雙指針一般用于處理有序數(shù)組合并，求交集、并集問題

349. 兩個數(shù)組的交集 - 力扣（LeetCode）

思路：分離雙指針

1. 兩個數(shù)組先排序。（）
2. 使用兩個指針分別指向兩個數(shù)組的第一個元素，即第一個指針指向第一個數(shù)組的第一個元素，第二個指針指向第二個數(shù)組的第一個元素。（）
3. 如果 $nums1[lef{t}_1]==nums2[lef{t}_2]$ 則將其加入答案數(shù)組（注意去重），并將 $lef{t}_1$ 和 $lef{t}_2=0$ 右移 （$lef{t}_1+=1$ 、$lef{t}_2+=1$）。
4. 如果 $nums1[lef{t}_1]<nums2[lef{t}_2]$ ，則 $lef{t}_1$ 右移 。
5. 如果 $nums1[lef{t}_1]>nums2[lef{t}_2]$ ，則 $lef{t}_2$ 右移 。
6. 返回答案。

代碼

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:nums1.sort()nums2.sort()left_1 = 0left_2 = 0res = []while left_1 < len(nums1) and left_2 < len(nums2):if nums1[left_1] == nums2[left_2]:if nums1[left_1] not in res:res.append(nums1[left_1])left_1 += 1left_2 += 1elif nums1[left_1] < nums2[left_2]:left_1 += 1elif nums1[left_1] > nums2[left_2]:left_2 += 1return res

2 滑動窗口基礎(chǔ)知識

2.1 滑動窗口算法介紹

滑動窗口算法（Sliding Window Algorithm）是一種常用的算法技巧，用于解決數(shù)組或字符串相關(guān)的問題。它的基本思想是維護一個窗口，通過在數(shù)組或字符串上滑動窗口，不斷更新窗口內(nèi)的狀態(tài)，從而解決問題。可以對窗口進行滑動操作、縮放操作，以及維護最優(yōu)解操作。

• 滑動操作：窗口向一個方向移動，常見的是向右側(cè)移動。
• 縮放操作：針對不固定長度的窗口，可以從左側(cè)縮小窗口長度，也可以從右側(cè)擴大窗口長度。

2.2 滑動窗口適用范圍

滑動窗口算法通常適用于線性數(shù)據(jù)結(jié)構(gòu)，如數(shù)組和字符串。它在處理大規(guī)模數(shù)據(jù)時特別有用，因為它可以通過滑動窗口的方式，僅對部分數(shù)據(jù)進行處理，而不需要遍歷整個數(shù)據(jù)集。這使得滑動窗口算法具有較低的時間復(fù)雜度，并且在實際應(yīng)用中常常能夠提供高效的解決方案。

按照窗口長度的固定情況，我們可以將滑動窗口題目分為以下兩種：

• 固定長度窗口：窗口大小是固定的。

• 不定長度窗口

  • 窗口大小是不固定的。

  • 求解最大的滿足條件的窗口。

  • 求解最小的滿足條件的窗口。

2.3 固定長度滑動窗口

固定長度滑動窗口是一種特殊的滑動窗口算法，它的窗口大小固定，不會隨著數(shù)據(jù)集的變化而變化。該算法通常用于需要對連續(xù)的數(shù)據(jù)序列進行處理的問題，如時間序列數(shù)據(jù)分析等。

固定長度滑動窗口的基本思想是：將數(shù)據(jù)序列分成若干個固定長度的子序列，然后對每個子序列進行處理。在處理每個子序列時，可以使用滑動窗口算法，通過移動窗口來更新子序列內(nèi)的狀態(tài)，從而得到最終的結(jié)果。

基本步驟

固定長度滑動窗口的步驟如下：

1. 初始化窗口的起始位置和結(jié)束位置，窗口大小固定。
2. 對于每個窗口內(nèi)的子序列，根據(jù)問題要求更新窗口內(nèi)的狀態(tài)。
3. 如果窗口滿足特定條件，記錄結(jié)果。
4. 繼續(xù)移動窗口的起始位置，重復(fù)上述步驟，直到遍歷完整個數(shù)據(jù)集。

代碼模板

left = 0
right = 0while right < len(nums):window.append(nums[right])# 超過窗口大小時，縮小窗口，維護窗口中始終為 window_size 的長度if right - left + 1 >= window_size:# ... 維護答案window.popleft()left += 1# 向右側(cè)增大窗口right += 1

2.4 不固定長度滑動窗口

不定長度滑動窗口算法（Sliding Window）：在給定數(shù)組 / 字符串上維護一個不定長度的窗口?？梢詫Υ翱谶M行滑動操作、縮放操作，以及維護最優(yōu)解操作。

基本步驟

1. 使用兩個指針 $left$、$right$。初始時，$left$、$right$ 都指向序列的第一個元素。即：$left=0$，$right=0$，區(qū)間 $[left,right]$ 被稱為一個「窗口」。
2. 將區(qū)間最右側(cè)元素添加入窗口中，即 window.add(s[right])。
3. 然后向右移動 $right$，從而增大窗口長度，即 right += 1。直到窗口中的連續(xù)元素滿足要求。
4. 此時，停止增加窗口大小。轉(zhuǎn)向不斷將左側(cè)元素移出窗口，即 window.popleft(s[left])。
5. 然后向右移動 $left$，從而縮小窗口長度，即 left += 1。直到窗口中的連續(xù)元素不再滿足要求。
6. 重復(fù) 2 ~ 5 步，直到 $right$ 到達序列末尾。

代碼模板

left = 0
right = 0while right < len(nums):window.append(nums[right])while 窗口需要縮小:# ... 可維護答案window.popleft()left += 1# 向右側(cè)增大窗口right += 1

參考文獻

• [1] https://datawhalechina.github.io/leetcode-notes/#/

—— END ——

---

如果以上內(nèi)容有任何錯誤或者不準確的地方，歡迎在下面 👇 留言。或者你有更好的想法，歡迎一起交流學(xué)習(xí)~~~

更多精彩內(nèi)容請前往 AXYZdong的博客