双指针

所谓双指针算法，就是指的是在遍历的过程中，不是普通的使用单个指针进行循环访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的
。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算，将时间复杂度从log(n^2)降到log(n).

(注意：这里的指针，并非专指c中指针的概念，而是指索引，游标或指针，可迭代对象等)！

数组求和

如果我给你两个有序数组a1,a2,a3......,an,b1,b2,b3......bn;我要你去找到两个下标,使它们对映的值之和等于一个特定值K，输出一对就ok了，当然我们可以轻易想到取用暴力枚举，用两重循环他的时间复杂度是log（n^2）,如果数据超过100000程序就超时了，我们可以用双指针算法把他降到log(n),这样就大大的节约了时间，在一秒钟的时间里面我们就可以处理1000000这么大的数组。下面看一下代码：
题目来源

模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

#include<iostream>
using namespace std;
const int N=1000010;
int a[N],b[N];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];

    for(int i=1,j=m;i<=n;i++){
       while(j>0&&a[i]+b[j]>k)
        {
             j--;
        }
        if(j>0&&a[i]+b[j]==k)
          cout<<i-1<<" "<<j-1<<endl;
    }
    return 0;
}

当然我们来理解一下，判断判断条件a[i]+b[i]>k,那么j–(向前移动)，出现等于时输出答案
我们画图理解一下：

最大子序列

当我们知道简单双指针遍历二个数组，让我们来理解遍历一个数组的情况

假设我给你一个数组a1,a2,a3....an，要你完成一下操作：

1.找到它的最大子序列；
2.求取它的重复元素个数；

你会怎么做？利用两重循环用if判断？其实思路没有错，我们只是要用双指针去优化他；

我们可以设立一个s[i]数组用于存储a[i]的个数，例如s[a[i]],如果有重复s[a[i]]+1，最后s[i]就是表示所有a[i]元素的状态。

模板：

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

题目来源

#include<iostream>
using namespace std;

const int N=100010;
int a[N],s[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int res=0;
   for(int i=0,j=0;i<n;i++){
        s[a[i]]++;
       while(s[a[i]]>1){
            s[a[j]]--;
            j++;

        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

题目要我们求最大长度，当然我们的一般是枚举循环取出有重复元素的子段，用双指针算法就是当i和j的两个索引值都在移动，给a[i]加上一个状态值，有一个我们就加一个，当他状态值大于1时，说明他有重复，就要移动j,重复该过程，选取以前的长度与现在长度的最大值。我们画一个简单图来理解：

双向扫描快速划分

我们已经理解了简单的双指针对一个数组和两个数组的处理，我们现在就可以轻松理解一下quick_sort，merge_sort模板；先看quick_sort与merge_sort的模板：
习题

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;// 判断排序的数字长度

    int i = l - 1, j = r + 1, x = q[l];
    //选取双指针i,j与 中间随机值
    while (i < j)
    {
        //进行判断比较大小并交换值
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        //注意！！！使用语言有没有swap方法（如果没有建议用位运算）
        else break;
    }
    //再将俩个部分（小于等于随机值||大于小于随机值）再次划分
    quick_sort(q, l, j),;
    quick_sort(q, j + 1, r);
}

习题

void merge_sort(int q[], int l, int r)
{
if (l >= r) return;//元素为0 or 1
int mid = l + r >> 1;//选取中间值
//划分区间
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
//确定双指针
int k = 0, i = l, j = mid + 1;
//条件一
while (i <= mid && j <= r)
//边界判断
if (q[i] < q[j]) tmp[k ] = q[i ];
else tmp[k ] = q[j ];
//条件二 
//左边没有循环完
while (i <= mid) tmp[k ] = q[i ];
//条件三
//右边没有循环完
while (j <= r) tmp[k ] = q[j ];
//合并
for (i = l,j = 0; i <= r; i , j ) q[i]= tmp[j];
}

其实这两个排序用基本思想是分治，遍历用来双指针。

奇偶排序

奇偶排序。题意是这样的，给定一个数组，数组中元素有奇数有偶数。要求对数组进行处理，使得数组的左边为奇数，右边为偶数

这个题目直接看上去，跟快速排序的划分十分类似，唯一不同的是，不需要返回索引。所以，简单的方式如下：

void function(int arr[],int n){
    int i = 0;
    int j = n-1;
        while(i<j){
        //if(i==j) break；刚开始打错了，谢谢提醒提醒
            while(i<j && arr[i]%2 == 1) i++;
            while(i<j && arr[j]%2 == 0) j--;
            if(i<j)swap(arr[i],arr[j]);
        }
}

结语

当然双指针算法作为基础算法，还有很多方面的利用，例如后面要总结的链表，双指针的运用就是优化暴力枚举，找到一些规律去解决问题，例如有效的去找到check条件；好了双指针就总结完了，后续的链表我会加进来，希望你有所收获，谢谢你阅读。

yxc老师的模板 链接

双指针算法
—— 模板题 AcWIng 799. 最长连续不重复子序列 799
AcWing 800. 数组元素的目标和 800
for (int i = 0, j = 0; i < n; i )
{
while (j < i && check(i, j)) j ;

// 具体问题的逻辑

}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作