双指针

剑指Offer-21

剑指Offer-22

• 链表倒数第k个数
• 两个指针间隔k

三指针

荷兰国旗问题

Leetcode-75 颜色分类问题

• 三种颜色 0， 1， 2
• 开始left、cur都在最左边， right在最右边
• left和cur交换之后，cur位置的取值，只能是0,1，所以必须cur++，否则可能出现left到cur右边的情况

• cur和right交换之后，cur位置取值，可能是0,1,2， 所有cur不动，进行下一轮比较

  class Solution {
    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public void sortColors(int[] nums) {
        int left = 0;
        int cur = 0;
        int right = nums.length - 1;
        int len = nums.length;
        while(cur <= right ) {
            // 交换 left 和 cur
            if(nums[cur] == 0) {
                swap(cur, left, nums);
                // 交换之后，left位置是0， 所以left++
                //System.out.println(nums[cur]);
                left++;
                // left肯定在cur左边，与cur交换位置的left的位置，肯定是0 或 1，所以可以cur++
                // 这里隐含了 nums[cur] == 0 nums[cur] == 1 两个条件
                cur++;
            } else if(nums[cur] == 2) {
                swap(cur, right, nums);
                right--;
                // 这里 没有cur++, 交换来的数字 可能 是 0 1 2 ,所以cur不动，再进行下一轮比较
            } else  cur++;
        }
    }
  }