Two pointers

思考一个问题，给一个数列（1,2,3,4,5,6），找出不同位置的数字相加等于x的数字的位置。

常规思路是枚举法，双循环，但是它的时间复杂度为O(n^2)当n的规模很大时不可以承受。

Two pointers 的时间复杂度仅为O(n)，效率高

#include<cstdio>
#include<iostream>
using namespace std;

int TP(int A[],int n,int x)//Two pointers函数，所给数的范围(0,n-1),x是所要的和
{
    int left=0,right=n-1;
    while(left<right)
    {
        if(A[left]+A[right]==x)
        {
            printf("%d %d\n",left,right);
            left++;
            right--;
        }
        else if(A[left]+A[right]<x)/
        {
            left++;
        }
        else
            right--;
    }
}

int main()
{
    const int n=6;
    int A[n]={1,2,3,4,5,6};
    TP(A,6,8);
    return 0;

}

序列合并问题：

将两个递增序列A,B合并成一个递增C数组

#include<cstdio>
#include<iostream>
using namespace std;

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)//A是否有剩余
        C[index++]=A[i++];
    while(j<m)//B是否有剩余
        C[index++]=B[j++];
    return index;//返回C长度
}

int main()
{
    const int n=5;
    const int m=3;
    int A[n]={1,2,3,5,6};
    int B[m]={1,4,8};
    int C[n+m];
    for(int a=0;a<merge(A,B,C,5,3);a++)
        printf("%d ",C[a]);
    return 0;
}

写给未来看的这些年的努力~~