双指针

双指针

同向双指针

能够实现跳跃寻找，适用于寻找含有某一特性区间，比如最长相同区间，最长不重复区间

不重复区间可以用一个数组t[N]来表示，如果其中元素大于1，说明有重复

int res=0,j=0;
for(int i=0;i<n;i++)
{
    t[a[i]]++;//记录个数
    while(j<i&&t[a[i]]>1) t[a[j++]]--;//改变区间
    if(i-j+1>res) res=i-j+1;
}

相同区间用第二个指针移动来寻找下一个不相同的位置，可计算出区间长度

int num=0;
char ans;
for(int i=0;i<s.size();)
{
    int j=i;
    while(j<s.size()&&s[j]==s[i]) j++;
    if(j-i>num) num=j-i,ans=s[i];
    i=j;
}

双向双指针

一个从前往后走，一个从后往前走

使得与暴力循环两个数组不同的是，j不会回退

例子:给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

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

中向双指针

两个指针从左右两侧开始移动直到相遇

例：快速排序中根据轴值划分，调整奇偶序列，翻转数组

while(i<j) //未相遇继续循环
{
    while(state) i++;
    while(state) j--;
    if(i<j) swap(x,y);
}