Two pointers notes

1. 同向双指针做partition的情况

    一个指针i是slow mover指向满足在右边的点，另一个指针j是fast mover一直往后走访问到需要往前移的点就把这个点和i调换，同时i++。i 最后指向的是右边第一个点，i其实是分界点。
   以下是一些题需要满足移动的情况：

    Move Zeroes:  nums[j] != 0

    Quick sort partitioning:  nums[j] < pivot
    Remove Duplicates from Sorted Array: nums[j] != nums[i]
    Remove Element: nums[j] != target value
    Kth Largest Element in an Array: partition, remember to swap start and i - 1.

 

    以上类型的题可以有一个模板如下：
     

        if (nums == null) return 0;
        int  i = 0; 
        for (int j = 0; j < nums.length; j++) {
            if (when nums[j] need to be moved to where i at) {
                nums[i++] = nums[j];
            }
        }

    slow pointer的左边是满足条件的区域。如果返回长度，就直接返回slow pointer的index。

2. 2sum 反向双指针
    基础模板是2 sum，follow up 要考虑如何去重复， 如何选取3 sum的基点。

•     3Sum: 2次去重复，一次在基点处，另一次在找到candidate的时候
•     3Sum Closest: 比3 sum 还简单，不需要去重复
•     3Sum Smaller: 候选答案是一个range
•     Valid Triangle Number: 选基点比较tricky, 也要考虑range