2. Two Pointer

Template

 Two pointer types:
• 对撞型 (2 sum 类 和 partition 类)
• 前向型 (窗口类, 快慢类)
• 两个数组,两个指针 (并行)

• “对撞型”或“相会型”

//Two sum

if (A[left] + A[right] > sum)
    right--;
    do something
else if (A[left] + A[right] < sum)
    left++;
    do something
else
    do something
    left++ or right--
    
// 灌水类型题目思路
if (A[left] > A[right])
    right--
else if (A[left] < A[right])
    left++
else
    left++ or right--

//Partition类模板

public int partition(int[] nums, int l, int r) {
    // 初始化左右指针和pivot
    int left = l, right = r;
    int pivot = nums[left];

    // 进行 partition
    while (left < right) {
        while (left < right && nums[right] >= pivot) {
            right--;
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        nums[right] == nums[left];
    }

    // 返还pivot点到数组里
    nums[left] = pivot;
    return left;
}

//Quick sort to call the partition function
public void quickSort(int[] nums, int l, int r) {
    if (l < r) {
        int pivotIndex = partition(nums, l, r);
        quickSort(nums, l, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, r);
    }
}


// Partition 的另外一个模板
public void swap(int[] nums, int x, int y) {
    int tmp = nums[x];
    nums[x] = nums[y];
    nums[y] = tmp;
}

public int partition(int[] nums, int left, int right) {

    Random rand = new Random();
    int pivotIndex = rand.nextInt((right - left) + 1) + left;
    // Init pivot
    int pivotValue = nums[pivotIndex];

    swap(nums, pivotIndex, right);

    // First index that nums[firstIndex] > pivotValue
    int firstIndex = left;

    for (int i = left; i <= right - 1; i++) {
        if (nums[i] < pivotValue) {
            swap(nums, firstIndex, i);
            firstIndex++;
        }
    }

    // Recover pivot to array
    swap(nums, right, firstIndex);
    return firstIndex;
}

• 快慢型

ListNode fast, slow;
fast = head;
slow = head;
while (fast!=null || fast.next!=null) {
    fast = fast.next.next;
    slow = slow.next;
}

Typical problems

• NSum problems

//Two sum on an ordered array
//Find an index pair from an ordered array that the sum of them equal to target, 
// return {-1, -1} if doesn't exist

 public int[] twoSum(int[] numbers, int target) {
    if (numbers == null || numbers.length == 0) {
        return new int[] { -1, -1};
    }
    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};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] {-1,-1};
}


//Three sum on an array that might contains duplicates
// Find all the triples that adds up to zero
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    Arrays.sort(nums);//注意，看数据集是否被sort了
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) { //去重
            continue;
        }
        int target = -nums[i];
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                //注意
                result.add(Arrays.asList(new Integer[]{nums[i], nums[left], nums[right]}));
                while (left < right && nums[left] == nums[left+1]) { //左去重
                    left++;
                }
                while (left < right && nums[right] == nums[right-1]) {//右去重
                    right--;
                }
                //注意别忘记
                left++;
                right--;
            }
        }
    }
    return result;
}