双指针算法

使用 i, j 两个变量，不会退的扫描一个或两个数组

朴素做法 — $O(n ^ 2)$

for(int i = 0; i < n; i ++){
    for(int j = 0; j < n; j ++)
}

双指针算法 ---- $O(n)$

for(int i=0,j=0;i<n;i++)
{
    while(j<i && check(i,j)) j++;
    //每道题目的具体逻辑
}

核心思想

将朴素做法$O(n ^ 2)$优化为$O(n)$

常用类型

类型1： 同时指向两个序列, 例如归并排序的归并过程
类型2： 同时指向一个序列, 例如快排

经典案例

最长连续不重复子序列
归并排序
快速排序
数组元素的目标和
区间覆盖

reference