歡迎拜訪：霧里看山-CSDN博客
本篇主題：算法思想之雙指針(一)
發布時間：2025.4.4
隸屬專欄：算法

雙指針算法介紹

常見的雙指針有兩種形式，一種是對撞指針，一種是快慢指針。

對撞指針：

?般?于順序結構中，也稱左右指針。

• 對撞指針從兩端向中間移動。一個指針從最左端開始，另一個從最右端開始，然后逐漸往中間逼近。
• 對撞指針的終止條件一般是兩個指針相遇或者錯開（也可能在循環內部找到結果直接跳出循環），也就是：
  • left == right （兩個指針指向同一個位置）
  • left > right （兩個指針錯開）

快慢指針：

又稱為龜兔賽跑算法，其基本思想就是使用兩個移動速度不同的指針在數組或鏈表等序列結構上移動。
這種方法對于處理環形鏈表或數組非常有用。
其實不單單是環形鏈表或者是數組，如果我們要研究的問題出現循環往復的情況時，均可考慮使用快慢指針的思想。
快慢指針的實現方式有很多種，最常用的?種就是：

• 在一次循環中，每次讓慢的指針向后移動一位，而快的指針往后移動兩位，實現一快一慢。

例題

移動零

題目鏈接

283. 移動零

題目描述

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

請注意 ，必須在不復制數組的情況下原地對數組進行操作。

示例 1:

輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]

示例 2:

輸入: nums = [0]
輸出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1
  

進階：你能盡量減少完成的操作次數嗎？

算法思路

在本題中，我們可以用一個 cur 指針來掃描整個數組，另一個 dest 指針用來記錄非零數序列的最后一個位置。根據 cur 在掃描的過程中，遇到的不同情況，分類處理，實現數組的劃分。在 cur 遍歷期間，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。

代碼實現

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();for(int dest = -1, cur = 0; cur < n; cur++){if(nums[cur] != 0){swap(nums[dest+1], nums[cur]);dest++;}}}
};

復寫零

題目鏈接

1089.復寫零

題目描述

給你一個長度固定的整數數組arr，請你將該數組中出現的每個零都復寫一遍，并將其余的元素向右平移。

注意：請不要在超過該數組長度的位置寫入元素。請對輸入的數組 就地 進行上述修改，不要從函數返回任何東西。
示例 1：

輸入：arr = [1,0,2,3,0,4,5,0]
輸出：[1,0,0,2,3,0,0,4]
解釋：調用函數后，輸入的數組將被修改為：[1,0,0,2,3,0,0,4]

示例 2：

輸入：arr = [1,2,3]
輸出：[1,2,3]
解釋：調用函數后，輸入的數組將被修改為：[1,2,3]

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 9

算法思路

如果從前向后進行原地復寫操作的話，由于 0 的出現會復寫兩次，導致沒有復寫的數被覆蓋掉。因此我們選擇從后往前的復寫策略。但是從后向前復寫的時候，我們需要找到最后一個復寫的數，因此我們的大體流程分兩步：

• i. 先找到最后一個復寫的數；
• ii. 然后從后向前進行復寫操作。

代碼實現

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int cur = 0, dest = -1;// 找到最后覆寫的數while(dest < n){if(arr[cur] == 0)dest+=2;elsedest++;if(dest >= n-1)break;cur++;}// 特殊情況處理if(dest == n){arr[n-1] = 0;dest-=2;cur--;            }// 進行復寫操作while(cur >= 0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur --;}else{arr[dest--] = arr[cur--];}}}
};

快樂數

題目鏈接

202.快樂數

題目描述

編寫一個算法來判斷一個數n是不是快樂數。
快樂數 定義為：

• 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
• 然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
• 如果這個過程 結果為 1，那么這個數就是快樂數。

如果n是 快樂數 就返回 true ；不是，則返回 false 。
示例 1：

輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

輸入：n = 2
輸出：false

提示：
1 <= n <= 231 - 1

算法思路

根據上述的題目分析，我們可以知道，當重復執行 x的時候，數據會陷入到一個循環之中。而快慢指針有一個特性，就是在一個圓圈中，快指針總是會追上慢指針的，也就是說他們總會相遇在一個位置上。如果相遇位置的值是1 ，那么這個數一定是快樂數；如果相遇位置不是1的話，那么就不是快樂數。

代碼實現

class Solution {
public:int BitSum(int n){int num = 0;while(n>0){int x = n %10;n /= 10;num+=x*x;}return num;}bool isHappy(int n) {int slow = n, fast = BitSum(n);while(slow != fast){slow = BitSum(slow);fast = BitSum(BitSum(fast));} return slow == 1;}
};

盛最多水的容器

題目鏈接

11. 盛最多水的容器

題目描述

給定一個長度為 n 的整數數組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。

找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

返回容器可以儲存的最大水量。

說明：你不能傾斜容器。

示例 1：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例 2：

輸入：height = [1,1]
輸出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

算法思路

設兩個指針 left ，right分別指向容器的左右兩個端點，此時容器的容積 :
v = (right - left) * min( height[right], height[left])
容器的左邊界為 height[left] ，右邊界為 height[right] 。
為了方便敘述，我們假設左邊邊界小于右邊邊界。
如果此時我們固定一個邊界，改變另一個邊界，水的容積會有如下變化形式：

• 容器的寬度?定變小。
• 由于左邊界較小，決定了水的高度。如果改變左邊界，新的水面高度不確定，但是?定不會超過右邊的柱子高度，因此容器的容積可能會增大。
• 如果改變右邊界，無論右邊界移動到哪里，新的水面的高度一定不會超過左邊界，也就是不會
  超過現在的水面高度，但是由于容器的寬度減小，因此容器的容積一定會變小的。

由此可見，左邊界和其余邊界的組合情況都可以舍去。所以我們可以 left++ 跳過這個邊界，繼續去判斷下?個左右邊界。

當我們不斷重復上述過程，每次都可以舍去大量不必要的枚舉過程，直到left 與 right 相遇。期間產生的所有的容積里面的最大值，就是最終答案。

代碼實現

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size()-1;int ret = 0;while(left < right){int v  = min(height[right], height[left]) * (right-left);ret = max(ret, v);if(height[left] < height[right])left++;elseright--;}return ret;}
};

?? 寫在最后：以上內容是我在學習以后得一些總結和概括，如有錯誤或者需要補充的地方歡迎各位大佬評論或者私信我交流！！！