对撞类，灌水类，two sum类

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

将时间复杂度从 O(n^2) -> O(n)

if(A[i]和A[j] 满足某个状态) {
    do something;
    j--; // 不用考虑[i+1, j-1] 和 j组成的pair
} else if(A[i]和A[j] 不满足某个状态) {
    do something;
    i++;
} else {
    do something;
    i++ or j--;
}

Two Sum

unsorted array 其实和two pointer无关，但是为了引出下一题就放在这儿了

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return new int[2];
        }

        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                return result;
            } else if(!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
        }

        return result;
    }
}

Two Sum II

sorted array

• 如果 nums[i] + nums[j] > target，那么 nums[i ~ j-1] + nums[j] > target.
• 因此 i,j 指向的不仅仅是元素，也代表了利用单调性，i,j 之间所有的 pair.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];

        if(numbers == null || numbers.length == 0) {
            return result;
        }

        int start = 0;
        int end = numbers.length - 1;

        while(start < end) {
            int sum = numbers[start] + numbers[end];

            if (sum == target) {
                result[0] = start + 1;
                result[1] = end + 1;
                return result;
            } else if(sum > target) {
                end--;
            } else {
                start++;
            }
        }

        return result;
    }
}

Container With Most Water

暴力解法就是找到所有的可能pair，计算他们之间的盛水容量，这是O(n^2)的。

利用木桶原理，盛水的最大容量取决于最短的那块板。两个指针分别置于头尾，这时候我们面临着移动长板还是短板的问题。 移动长板没有意义的，因为移动任意一个指针都会导致宽度减小，而长度没有变化（取决于短板），所以面积是必然减小的。所以这时候我们应该移动短板。

public class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }

        int start = 0;
        int end = height.length - 1;
        int max = 0;
        while(start < end) {
            // update max area
            max = Math.max(max, Math.min(height[start], height[end]) * (end - start));
            if(height[start] < height[end]) {
                start++;
            } else {
                end--;
            }
        }
        return max;
    }

    // second version 
    // 应对大数据集的prune 写法
    // 优化方法
    public int maxArea(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }

        int start = 0;
        int end = height.length - 1;
        int max = 0;
        while(start < end) {
            // update max area
            int min = Math.min(height[start], height[end]);
            max = Math.max(max, min * (end - start));
            // 如果比最小值还要小，那么这个值就没必要再去计算了
            while(start < end && height[start] <= min) start++;
            while(start < end && height[end] <= min) end--;
        }
        return max;
    }
}