对撞指针 O(n)

算法的根本是，证明不用扫描多余状态

给一个数组A
int left = 0, right = A.length - 1;
while (left < right) {
    if (A[left]和A[right]满足某一个条件) {
        //做一些事情
        right--; //不用考虑[left+1, right-1]中元素和right组成的区间
    } else if (A[left]和A[right]不满足某一条件) {
        //做一些事情
        left++;  //不用考虑left和[left+1, right-1]中元素组成的区间
    } else {  //一般不会出现
        left++ or right--;
    }
}

Partition指针 O(n)

int partition(vector<int>& nums, int l, int r) {
    // 初始化指针和pivot
    int left = l, right =r;
    int pivot = nums[left]; //选最左点为pivot，不是最好的方法
    // 进行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;
}

前向型指针：窗口类和快慢类 O(n)

关键是证明两个指针都是向前走，不需要回退

于sliding window不同的是窗口是所求而不是固定的值

for (int i = 0; i < n; ++i) {
    while (j < n && 满足某些条件）{
        j++；
        更新j状态；
        更新目标状态；
    }
    更新i状态；
}

两个数组两个指针