# 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;
}
``````

### 相会型指针题目

• 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循环而来
* 外层指针依然是依次遍历
* 内层指针证明是否需要回退
``````
``````for (i = 0; i < n; i++) {
while (j < n) {
if (满足条件)
j++
更行j状态
else (不满足条件)
break
}
更新i状态
}
``````

### 快慢类

``````ListNode fast, slow;
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

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: