双指针

原理

双指针算法一般都可以暴力求解，但是暴力求解的时间复杂度一般为O(n^2)，通过优化使用双指针可以将其时间复杂度降低为O(n)。优化的本质是寻找i和j变化的单调性，如果某个指针在单调条件之下不可能再继续遍历，就可以省略那些遍历。

有些情况下，需要先构造性质比较好的数列，之后才能应用双指针算法。

双指针算法主要有2种：

两个指针均从左端点开始，维护一个窗口。当窗口内元素满足某一性质的时候可以计算答案，如果不满足性质的时候，左侧窗口指针开始收缩，直到满足性质或者左右指针重合，之后再计算答案。这里一般维护的是个数等信息，因为需要右指针右移增大，而左指针右移减小才行。
左指针从左开始，右指针从右开始。维护的窗口一般都是单调的，性质是维护两者之和，这样左指针右移后和会增大，右指针左移后和会减小。

模板

for (int i = 0, j = 0; i < n; i ++ )
{
    //如果要维护集合，在这里维护即可
    while (j < i && check(i, j)) j ++ ;
    //while(j <= i && check(i, j))可以判断当i == j时是否还有不满足性质的情况要被剔除
    //具体逻辑
}