---
tags: 演算法, LeetCode
disqus: HackMD
---

# Two Pointers

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

此演算法可以幫助我們對某些資料結構做某種方式的排序，例如[977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)或[283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)等等，$$它可以幫助我們將時間複雜度從O(n^2) 或是 O(n^3) 縮減成 O(n)$$

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

## 左右指標

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

(圖片來自[Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e))

### 範例題目

利用leetcode[167. Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)來做練習，這題題目會跟[1. Two Sum](https://leetcode.com/problems/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](https://leetcode.com/problems/squares-of-a-sorted-array/)

[283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)

[344. Reverse String](https://leetcode.com/problems/reverse-string/)

[557. Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)

## 快慢指標

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

(圖片來自[Basics of Two Pointers Technique](https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e))

### 範例題目

利用[876. Middle of the Linked List](https://leetcode.com/problems/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](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

## 更多例題

[leetcode two-pointers tag](https://leetcode.com/tag/two-pointers/)

By. @joe94113