算法笔记(6)| two pointers

two pointers是算法编程中一种非常重要的思想，它的主要内容是利用问题本身与序列的特性，使用两个下标i，j对序列进行扫描，以较低的复杂度解决问题。

1.序列求和问题

给定一个递增的序列和一个数M，要求在序列里面找到两个数，并让它们的和等于M

这道题目的一般解法就是使用两个循环来遍历查找符合要求的数，但是注意到这道题所给出的序列是递增的，因此使用循环遍历查找的方法没有完全利用到题目，并且时间复杂度为(n^2)，在针对较大的序列来说是不可取的。

利用two pointers思想，我们可以对序列设置两个下标i，j。让i指向序列的开始位置，j指向序列的末尾位置，然后根据两者所指向数的和与M的大小进行比较来决定它们的移动方向。

void twoPointers(int a[],int n){  //数组以及数组的大小
    int i=0,j=n-1;
    while(i<j){
        if(a[i]+a[j]==M){
            printf("%d %d\n",a[i],a[j]);
            i++;
            j--;
        }
        else if(a[i]+a[j]<M){
            i++;
        }
        else if(a[i]+a[j]>M){
            j--;
        }
    }
}

使用two pointers方法所需要的时间复杂度为O(n)。

2.序列合并问题

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

对这道题同样使用two pointers思想：

void twoPointers(int a[],int b[],int c[],int n,int m){  //n和m代表a[]与b[]的长度
    int i=0,j=0,k=0;
    while(i<n && j<m){
        if(a[i]<=b[j]){
            c[k]=a[i];
            k++;
            i++;
        }
        else if(a[i]>b[j]){
            c[k]=b[j];
            k++;
            j++;
        }
    }
    while(i<n){
        c[k]=a[i];
        i++;
        k++;
    }
    while(j<m){
        c[k]=b[j];
        k++;
        j++:
    }
}