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

1.1 雙指針簡介

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

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

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

雙指針?biāo)惴ㄍǔ＞哂休^低的時(shí)間復(fù)雜度，并且可以在一次遍歷中完成任務(wù)，因此在很多問題中都有很好的應(yīng)用。

1.2 左右指針（對(duì)撞指針）

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

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

基本步驟

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

偽代碼模板

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

適用范圍

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

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

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

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

1.3 快慢指針

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

基本步驟

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

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

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

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

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

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

   • 例如，在鏈表中找到中間節(jié)點(diǎn)的問題中，當(dāng)快指針到達(dá)鏈表末尾時(shí)，慢指針?biāo)傅墓?jié)點(diǎn)就是中間節(jié)點(diǎn)。

偽代碼模板

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

適用范圍

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

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

3. 鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)的查找：快慢指針可以用于定位鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)?？熘羔樝纫苿?dòng)k個(gè)位置，然后快慢指針同時(shí)向前移動(dòng)，當(dāng)快指針到達(dá)鏈表末尾時(shí)，慢指針?biāo)傅墓?jié)點(diǎn)就是倒數(shù)第k個(gè)節(jié)點(diǎn)。

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

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

1.4 分離雙指針

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

基本步驟

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

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

   1. 兩個(gè)指針同時(shí)右移，。

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

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

3. 當(dāng)其中一個(gè)數(shù)組遍歷完時(shí)或者滿足其他特殊條件時(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. 兩個(gè)數(shù)組的交集 - 力扣（LeetCode）

思路：分離雙指針

1. 兩個(gè)數(shù)組先排序。（）
2. 使用兩個(gè)指針分別指向兩個(gè)數(shù)組的第一個(gè)元素，即第一個(gè)指針指向第一個(gè)數(shù)組的第一個(gè)元素，第二個(gè)指針指向第二個(gè)數(shù)組的第一個(gè)元素。（）
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 滑動(dòng)窗口基礎(chǔ)知識(shí)

2.1 滑動(dòng)窗口算法介紹

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

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

2.2 滑動(dòng)窗口適用范圍

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

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

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

• 不定長度窗口

  • 窗口大小是不固定的。

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

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

2.3 固定長度滑動(dòng)窗口

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

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

基本步驟

固定長度滑動(dòng)窗口的步驟如下：

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

代碼模板

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

2.4 不固定長度滑動(dòng)窗口

不定長度滑動(dòng)窗口算法（Sliding Window）：在給定數(shù)組 / 字符串上維護(hù)一個(gè)不定長度的窗口?？梢詫?duì)窗口進(jìn)行滑動(dòng)操作、縮放操作，以及維護(hù)最優(yōu)解操作。

基本步驟

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

代碼模板

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

參考文獻(xiàn)

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

—— END ——

---

如果以上內(nèi)容有任何錯(cuò)誤或者不準(zhǔn)確的地方，歡迎在下面 👇 留言?；蛘吣阌懈玫南敕?#xff0c;歡迎一起交流學(xué)習(xí)~~~

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