two pointers

【问】

给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使得它们的和恰好是M

【分析】

如果使用二重循环肯定会超时的

时间复杂度O（n^2）

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

【问题2】

假设有两个递增序列A和B，要求将它们合并成一个递增序列C

【分析】

int merge(int A[],int B[],int C[],int n,int m)
{
    int i=0,j=0,index=0;
    while(i<n&&j<m)
    {
        if(A[i]<=B[j])
        {
            C[index++]=A[i++];
        }
        else
        {
            C[index++]=B[j++];
        }
    }
    while(i<n)
        C[index++]=A[i++};
    while(j<m)
        C[index++]=B[j++];
    return index;
}

 总之，two pointers就是利用问题本身与序列的特性

使用下标i、j对序列进行扫描

以较低的复杂度来解决问题