2 pointer 算法

FeastSC

背景介绍

2 pointer算法经常被使用为一种优化算法，其对空间和时间均有不错的优化效果。这里的pointer指的是数据的index，又或者为链表中的节点。

2 pointer 算法能够通过两个pointer的移动，快速排除错误组合范围，从而以较优的方法找到正确解。

2 pointer的算法类型

1. 2 pointer 对向移动

在这种类型的问题中，我们一般设置pointer在数组起始位置和结束位置，通过移动pointer向相反的方向移动来寻求解。


Two Sum II - 输入为有序数组

题目链接：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

给一个有序数组，以及一个目标数字。要求找出其中的两个数之和等于这个目标数字的index。

这个题目虽然也可以使用和Two Sum I中类似的解法，但由于输入数组为有序数组，我们则可以利用two pointer的算法进一步优化空间复杂度。将Two Sum I中的解法的空间复杂度将为O(1)。算法思路如下： 1. 初始化两个pointer，left和right分别指向数组的初始和末尾位置。 2. 求left和right在数组中指向数字的和。 3. 如果这个和等于目标数字，则退出程序返回结果。 4. 如果这个和大于数字，则移动right指针向左。 5. 如果这个和小于数字，则移动left指针向右。
实现代码如下：
// 一段优雅的代码
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null) return null;

        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int sum =  numbers[left] + numbers[right];

            if (sum == target) {
                return new int[] {left + 1, right + 1};
            }

            // If sum > target, move right pointer
            if (sum > target) {
                right--;
            }
            // Otherwise, move left pointer
            else {
                left++;
            }
        }

        return null;
    }
}通过移动left和right的指针不断逼近目标数值，缩小搜索范围，直到找到正确答案。关于这种方法为什么可行，很多博客都没有说明，我提供的证明如下。


我们先证明为什么当nums[left] + nums[right] < target, 我们可以缩小范围为[left+1, right]。为什么不可能是left和区间[right + 1, end]？ 首先我们推算一下nums[left] + nums[right + 1]和target的大小比较。我们假设nums[left] + nums[right + 1] < target，那么指针不会移动到left的位置，而是会移动到left+1和right+1的位置，这样指针也不久不可能出现left和right这两个位置的组合。所以nums[left] + nums[right + 1] > target。所以也就证明了答案区间不在left和区间[right + 1, end]。
同理也可以用于证明nums[left] + nums[right] > target的场景。
Trapping Rain water

题目链接：https://leetcode.com/problems/trapping-rain-water/

输入为一组整型数组，代表一段地势的海拔高度。问在下雨过后，这段地势可以蓄多少水

这个题目需要先找到计算每个位置上能够存储多少水的算法。我们可以很快分析发现，每根柱子的蓄水量是由min(leftMax, rightMax) - height[current]计算得来。比如图示中index在2的位置，地势高度为0，能够存1个单位的水。这个水量是由左右两边最大值中的最小值所决定的。左边最大值为1，右边最大值为3。他们两者中的最小值为1，所以这个位置的蓄水量为1减去当前高度0。
这个题目如果暴力求解，需要从每个位置向左和向右遍历一边去找到两边的最值。时间复杂度为O(n^2)。通过动态规划优化这个过程，我们发现只要我们知道左右两边的极值情况就可以算出来当前位置的左右两边的极值情况。这个方法我就不在展开。动规可以通过扫两边数组，以O(n)时间复杂度和O(n)空间复杂度完成计算。
虽然动态规划的思路规划已经很好了，但2 pointer可以这个过程进行更近一步的优化。2 pointer可以通过一次遍历，O(1)空间复杂度完成求解。这个题目同样是从两边向中间聚合，通过数学规律，省去搜索范围。算法的过程如下：

• 设置指针left=0，right=heights.length - 1, leftMax = heights[0], rightMax = height[heights.lenght - 1]。这里是left和right为左右向中间聚合的指针。leftMax代表了left到最左边整个区间中的最大值。rightMax代表了right到右边区间中的最大值。
  
• 在left < right的情况，重复一下步骤
  
• 如果height[left] > leftMax，则更新leftMax。同理更新rightMax。
  
• 如果leftMax < rightMax，则更新结果res += leftMax - heights[left]。同时更新left = left + 1。这么做的原因是rightMax的值只会越来越大。如果此时leftMax已经小于rightMax了，那么当前位置的左右极值中的最小值一定为leftMax
  
• 如果leftMax > rightMax，同理更新res += rightMax - heights[right]。right = right - 1。
  

算法的代码如下：
// 一段优雅的代码
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;

        int leftMax = height[0], rightMax = height[height.length - 1];
        int left = 0, right = height.length - 1;
        int res = 0;

        while(left <= right) {
            if (height[left] > leftMax) {
                leftMax = height[left];
            }

            if (height[right] > rightMax) {
                rightMax = height[right];
            }

            if (leftMax < rightMax) {
                // 此时leftMax决定了当前位置的存水量
                res += leftMax - height[left];
                left++;
            } else {
                // 此时rightMax决定了当前位置的村水量
                res += rightMax - height[right];
                right--;
            }
        }

        return res;
    }
}以不同的速度相同方向移动pointer求解

找到链表中的中间数值

题目链接：https://leetcode.com/problems/middle-of-the-linked-list/
普通解决这个问题的思路是先遍历链表找到链表的数据的长度，然后第二次遍历找到位于链表中间位置的节点。2 pointer算法可以通过两个运行不同速度的节点遍历数组。移动快的节点移动速度是运行慢的节点移动速度的两倍。最后移动慢的节点的位置就是我们要求的最终答案。代码如下：
class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;

        ListNode fastRunner = head, slowRunner = head;

        while (fastRunner != null && slowRunner != null) {
            if (fastRunner.next == null || slowRunner.next == null) {
                return slowRunner;
            }

            slowRunner = slowRunner.next;
            fastRunner = fastRunner.next;

            if (fastRunner.next != null) {
                fastRunner = fastRunner.next;
            }
        }

        return null;
    }
}有用的链接

• https://afteracademy.com/blog/what-is-the-two-pointer-technique