对撞型，灌水类

双指针算法普遍分为三种

• 对撞类

  • two sum 类，partition 类

• 窗口类

• 并行型

• Princeton 公开课的课件，讲 2-way 和 3-way partitioning

• 掌握 3-way partition 和 k-way partition.

对撞型指针的本质是，不需要扫描多余的状态。在两边指针的判断之后，可以直接跳过其中一个指针与所有另外一面 index 组成的 pair.

Two Sum II

这道题如果暴力搜索的话，需要考虑的 pair 个数显然是 O(n^2). 但是用对撞型指针，可以有效跳过/剪枝不合理的 pair 组合。

排序之后的数组具有了单调性，两根指针的移动就代表了“增加”和“减少”。这种单调性保证了一条重要性质：

• 如果 nums[i] + nums[j] > target，那么 nums[i ~ j-1] + nums[j] > target.

• 因此 i,j 指向的不仅仅是元素，也代表了利用单调性，i,j 之间所有的 pair.

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    public int twoSum2(int[] nums, int target) {
        // Write your code here
        if(nums == null || nums.length == 0) return 0;

        Arrays.sort(nums);
        int count = 0;

        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            if(nums[left] + nums[right] <= target){
                left ++;
            } else {
                count += right - left;
                right --;
            }
        }

        return count;
    }
}

Triangle Count

总的思路对了，但是一开始的做法掉到了坑里，就是用 i = 1 to n 做最外循环，j 和 k 都在 i 后面。

• 这种思路的问题是，想 num[i] + num[j] > num[k]的话，如果当前条件不满足，j++ 和 k-- 都可以是对的。就违反了双指针不同程度上利用的单调性，一次只把一个指针往一个方向推，而且不回头。

• 所以顺着这个问题想，如果我们最外围遍历的是 k，而 i, j 都处于 k 的左面，那么每次就只有一个正确方向，挪动一个指针可以保证正确性了，即让 num[i] + num[j] 变大，或者变小。

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
        // write your code here
        Arrays.sort(S);
        int count = 0;

        for(int k = 0; k < S.length; k++){
            int i = 0;
            int j = k - 1;
            while(i < j){
                if(S[i] + S[j] <= S[k]){
                    i ++;
                } else {
                    count += j - i;
                    j --;
                }
            }
        }

        return count;
    }
}

Container With Most Water

这种“灌水”类问题和双指针脱不开关系，都要根据木桶原理维护边界；在矩阵中是外围的一圈高度，在数组中就是左右两边的高度。

• 因为最低木板的高度决定水位，高位的木板有着另一种单调性，即高位木板向里移动的所有位置，形成的 container 水量都小于原来位置。

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: an integer
     */
    public int maxArea(int[] heights) {
        // write your code here
        if(heights == null || heights.length == 0) return 0;
        int max = 0;
        int left = 0;
        int right = heights.length - 1;

        while(left < right){
            int width = right - left;
            int curArea = Math.min(heights[left], heights[right]) * width;
            max = Math.max(max, curArea);

            if(heights[left] < heights[right]){
                left ++;
            } else {
                right --;
            }
        }

        return max;
    }
}

Trapping Rain Water

木桶原理的算法版，最两边的板子形成一个木桶，由两块板子最低的那块决定水位。每次都从两边最低的方向向里扫描。

• 因为 i,j 当前高度未必是当前左右两边最高高度，每次更新的时候要注意维护下。

public class Solution {
    public int trap(int[] height) {
        if(height == null || height.length <= 2) return 0;
        int trapped = 0;
        int i = 0;
        int j = height.length - 1;

        int leftMax = height[i];
        int rightMax = height[j];

        while(i < j){
            if(leftMax < rightMax){
                if(i + 1 < height.length && height[i + 1] < leftMax){
                    trapped += leftMax - height[i + 1];
                }
                i++;
                leftMax = Math.max(leftMax, height[i]);
            } else {
                if(j - 1 >= 0 && height[j - 1] < rightMax){
                    trapped += rightMax - height[j - 1];
                }
                j--;
                rightMax = Math.max(rightMax, height[j]);
            }
        }

        return trapped;
    }
}