Two Pointers

Summary

 两个指针
• 对撞型 (2 sum 类 和 partition 类)
• 前向型 (窗口类, 快慢类)
• 两个数组,两个指针 (并行)

模板
• 2 Sum类模板
• Partition 类模板
• 窗口类模板

1. “对撞型”或“相会型”

Two Sum类题目思路

if (A[i] + A[j] > sum)
    j--;
    do something
else if (A[i] + A[j] < sum)
    i++;
    do something
else
    do something
    i++ or j--

灌水类型题目思路

if (A[i] > A[j])
    j--
else if (A[i] < A[j])
    i++
else
    i++ or j--

这一类通过对撞型指针优化算法，根本上其实要证明就是不用扫描多余状态

// Give an array arr[]
int left = 0;
int right = arr.length - 1;

while(left < right) {
    if(arr[left] 和 arr[right] 满足某一条件) {
        // Do something
        right --; // 不用考虑[left + 1, right - 1] 和 right 组成的pair
    } else if (arr[left] 和 arr[right] 不满足某一条件) {
        left ++; // 不用考虑[left + 1, right - 1] 和 left 组成的pair
    }
}

Partition类模板

public int partition(int[] nums, int l, int r) {
    // 初始化左右指针和pivot
    int left = l, right = r;
    int pivot = nums[left];

    // 进行 partition
    while (left < right) {
        while (left < right && nums[right] >= pivot) {
            right--;
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        nums[right] == nums[left];
    }

    // 返还pivot点到数组里
    nums[left] = pivot;
    return left;
}

Partition 另一种模板

public void swap(int[] nums, int x, int y) {
    int tmp = nums[x];
    nums[x] = nums[y];
    nums[y] = tmp;
}

public int partition(int[] nums, int left, int right) {

    Random rand = new Random();
    int pivotIndex = rand.nextInt((right - left) + 1) + left;
    // Init pivot
    int pivotValue = nums[pivotIndex];

    swap(nums, pivotIndex, right);

    // First index that nums[firstIndex] > pivotValue
    int firstIndex = left;

    for (int i = left; i <= right - 1; i++) {
        if (nums[i] < pivotValue) {
            swap(nums, firstIndex, i);
            firstIndex++;
        }
    }

    // Recover pivot to array
    swap(nums, right, firstIndex);
    return firstIndex;
}

• RosettaCode: Quickselect Algorithm

• Code Scream: The Partition Algorithm - Used For Quick-Select and Quick-Sort

• GeekViewpoint: Quickselect: Kth Greatest Value

• 被忽视的 partition 算法

相会型指针题目

• 2 Sum 类 （通过判断条件优化算法）

  • 3 Sum Closest

  • 4 Sum

  • 3 Sum

  • Two sum II

  • Triangle Count

  • Trapping Rain Water

  • Container With Most Water

• Partition 类

  • Partition-array

  • Sort Colors

  • Partition Array by Odd and Even

  • Sort Letters by Case

  • Valid Palindrome

  • quick sort\/ quick select\/ nuts bolts problem\/wiggle sort II

2. 前向型或者追击型

窗口类

窗口类指针移动模板

通过两层for循环改进算法 --- 不同于sliding window

优化类型:

* 优化思想通过两层for循环而来
* 外层指针依然是依次遍历
* 内层指针证明是否需要回退

for (i = 0; i < n; i++) {
    while (j < n) {
        if (满足条件)
            j++
            更行j状态
        else (不满足条件)
            break
    }
    更新i状态
}

快慢类

ListNode fast, slow;
fast = head.next;
slow = head;
while (fast != slow) {
    if(fast==null || fast.next==null)
        return false;
    fast = fast.next.next;
    slow = slow.next;
}
return true;

前向型指针题目

• 窗口类

  • Remove Nth Node From End of List

  • minimum-size-subarray-sum

  • Minimum Window Substring

  • Longest Substring with At Most K Distinct Characters

  • Longest Substring Without Repeating Characters

  • Longest Repeating Character Replacement

• 快慢类

  • Find the Middle of Linked L

两个数组两个指针

两个数组各找一个元素, 使得和等于target

1. 找一种

2. 找全部种类

From @LeetCode

Two-pointer Technique - Scenario I (相会型)

One of the typical scenarios to use two-pointer technique is you want to:

Iterate the array from two ends to the middle.

So that you can use the two-pointer technique:

One pointer starts from the beginning while the other pointer starts from the end.

This technique is often used in a sorted array.

Two-pointer Technique - Scenario II （快慢型）

two pointers with different steps to solve problems.

Scenario:

One slow-runner and one fast-runner at the same time.

The key to solving this kind of problems is to

Determine the movement strategy for both pointers.

Similar to the previous scenario, you might sometimes need to sort the array before using the two-pointer technique. And you might need a greedy thought to determine your movement strategy.

应用场景

Two Pointer Technique can be used to solve:

• Slow-pointer and fast-pointer problem in Linked List

• Sliding Window Problem

Sliding Window Problem

904.Fruit Into Baskets

424.Longest Repeating Character Replacement