6/13, Two Pointers, 对撞型，灌水/two sum

双指针算法普遍分为三种

• 对撞类

  • 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] 变大，或者变小。

• left.....right...K; n[left]+n[right]>n[k]

• 不用去重复, 有等边三角形的存在

    public int triangleCount(int S[]) {
        // write your code here
        Arrays.sort(S); int ans=0;
        for(int i=2;i<S.length;i++){
            int left = 0; int right = i-1;
            while(left<right){
                if(S[left]+S[right]<=S[i]) left++;
                else{
                    ans+=(right-left); right--;   
                }
            }
        }
        return ans;
    }

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

Shortest Unsorted Continuous Subarray

核心在于two pointers，开始只考虑了nums[i]>nums[i+1], 即使后面的元素递增，如果小于已扫过的Max，right point也需要移动。忽略了[1,2,4,5,3]这个case，只排序5，3，后面扫到的元素也有可能小于前面扫过的元素，需要排序[4,5,3]。

参考论坛上的解法，最简单有效的方式是从两边用two pointer说的方式扫。排序的核心就是“后面的元素总要比前面的元素大”，换一种说法就是“后面出现的最小值要比前面的元素大，前面出现的最大值要比后面的元素小”，想到了这里，问题解决。

正确打开姿势是开一个max pointer，min pointer，max从前往后扫，min从后往前扫，如果当前nums[i]没法作max value，当前end＝i；如果当前nums[nums.length-i-1]没法作min value，当前start＝nums.length-i-1。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int max = nums[0]; int min = nums[nums.length-1]; int start = 0; int end = -1;
        for(int i=1;i<nums.length;i++){
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[nums.length-i-1]);
            if(max>nums[i])
                end = i;
            if(min<nums[nums.length-i-1])
                start = nums.length-i-1;
        }
        return end-start+1;
    }
}