什么是雙指針（對撞指針、快慢指針）

雙指針，指的是在遍歷對象的過程中，不是普通的使用單個指針進行訪問，而是使用兩個相同方向（快慢指針）或者相反方向（對撞指針）的指針進行掃描，從而達到相應的目的。

換言之，雙指針法充分使用了數組有序這一特征，從而在某些情況下能夠簡化一些運算。

在LeetCode題庫中，關于雙指針的問題還是挺多的。雙指針

截圖來之LeetCode中文官網

用法

對撞指針

對撞指針是指在有序數組中，將指向最左側的索引定義為左指針(left)，最右側的定義為右指針(right)，然后從兩頭向中間進行數組遍歷。

對撞數組適用于有序數組，也就是說當你遇到題目給定有序數組時，應該第一時間想到用對撞指針解題。

偽代碼大致如下：

function fn (list) {var left = 0;var right = list.length - 1;//遍歷數組while (left <= right) {left++;// 一些條件判斷 和處理... ...right--;} }

舉個LeetCode上的例子：

以LeetCode 881救生艇問題為例

由于本題只要求計算出最小船數，所以原數組是否被改變，和元素索引位置都不考慮在內，所以可以先對于給定數組進行排序，再從數組兩側向中間遍歷。所以解題思路如下：

對給定數組進行升序排序

初始化左右指針

每次都用一個”最重的“和一個”最輕的“進行配對，如果二人重量小于Limit，則此時的”最輕的“上船，即（left++）。不管”最輕的“是否上船，”最重的“都要上船，即（right--）并且所需船數量加一，即（num++）

代碼如下：

var numRescueBoats = function(people, limit) {people.sort((a, b) => (a - b));var num = 0let left = 0let right = people.length - 1while (left <= right) {if ((people[left] + people[right]) <= limit) {left++}right--num++}return num };

---

快慢指針

快慢指針也是雙指針，但是兩個指針從同一側開始遍歷數組，將這兩個指針分別定義為快指針（fast）和慢指針（slow），兩個指針以不同的策略移動，直到兩個指針的值相等（或其他特殊條件）為止，如fast每次增長兩個，slow每次增長一個。

以LeetCode 141.環形鏈表為例,，判斷給定鏈表中是否存在環，可以定義快慢兩個指針，快指針每次增長一個，而慢指針每次增長兩個，最后兩個指針指向節點的值相等，則說明有環。就好像一個環形跑道上有一快一慢兩個運動員賽跑，如果時間足夠長，跑地快的運動員一定會趕上慢的運動員。

解題代碼如下：

/*** Definition for singly-linked list.* function ListNode(val) {* this.val = val;* this.next = null;* }*//*** @param {ListNode} head* @return {boolean}*/ var hasCycle = function(head) {if (head === null || head.next === null) {return false}let slow = headlet fast = head.nextwhile (slow !== fast) {if (fast === null || fast.next === null) {return false}slow = slow.nextfast = fast.next.next}return true };

再比如LeetCode 26 刪除排序數組中的重復項，這里還是定義快慢兩個指針。快指針每次增長一個，慢指針只有當快慢指針上的值不同時，才增長一個（由于是有序數組，快慢指針值不等說明找到了新值）。

真實代碼：

var removeDuplicates = function (nums) {if (nums.length === 0) {return 0;}let slow = 0;for (let fast = 0; fast < nums.length; fast++) {if (nums[fast] !== nums[slow]) {slow++;nums[slow] = nums[fast];}}return slow + 1; };

總結

當遇到有序數組時，應該優先想到雙指針來解決問題，因兩個指針的同時遍歷會減少空間復雜度和時間復雜度。

歡迎關注微信公眾號——【較真的前端

相關題目

• LeetCode.141.環形鏈表
• LeetCode.026.刪除數組中重復的項
• LeetCode.881.救生艇

參考文獻

• 《LeetBook》雙指針
• 【算法總結--數組相關】雙指針法的常見應用。
• 1.4.2 雙指針技巧（二）

總結

以上是生活随笔為你收集整理的指针 是否相同_算法一招鲜——双指针问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。