Two Pointers

Two Pointers常用在搜尋，他在一個給定的資料結構中做循環並給定兩個指針，用來解決編碼上的問題，常用在字串，陣列或鏈結串列 (Linked list)中。

此演算法可以幫助我們對某些資料結構做某種方式的排序，例如977. Squares of a Sorted Array或283. Move Zeroes等等，

$$\mathrm{它}\mathrm{可}\mathrm{以}\mathrm{幫}\mathrm{助}\mathrm{我}\mathrm{們}\mathrm{將}\mathrm{時}\mathrm{間}\mathrm{複}\mathrm{雜}\mathrm{度}\mathrm{從}O(n^2)\mathrm{或}\mathrm{是}O(n^3)\mathrm{縮}\mathrm{減}\mathrm{成}O(n)$$

而根據字串或陣列是否有排序，利用Two Pointers演算法，時間複雜度最差為O(n logn)更好為O(n)。

左右指標

一個從頭開始，另一個從結尾

(圖片來自Basics of Two Pointers Technique)

範例題目

利用leetcode167. Two Sum II - Input Array Is Sorted來做練習，這題題目會跟1. Two Sum有點相似，但作法有限制，廢話不多說先來看題目。

題目說明

給定一個非降序排序的數組，需要找到哪兩個索引位置的值加起來會等於target，並將其索引位置加一數組返回[index1 + 1, index2 + 1]

1. 只能使用恆定的記憶體
2. 不能兩次使用相同的元素
3. 1 <= index1 < index2 <= numbers.length

圖解

利用Example 1來做分解

解題

將上述圖解轉換成程式碼

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        let sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
};

更多相關練習題目

977. Squares of a Sorted Array

283. Move Zeroes

344. Reverse String

557. Reverse Words in a String III

快慢指標

相同的方向但是一個速度慢一個速度快

(圖片來自Basics of Two Pointers Technique)

範例題目

利用876. Middle of the Linked List做練習

題目說明

給定一個鏈結串列，回傳一個鏈結串列的中間節點，假如有兩個中間節點則回傳第二個中間節點。

圖解

利用快慢指標解題

解題

將上述圖解轉換成程式碼

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

更多相關練習題目

19. Remove Nth Node From End of List

更多例題

leetcode two-pointers tag

By. @joe94113