// two pointers的使用是建立在**有序排列**的基础上的。

对于给定一个**递增**正整数序列和一个正整数M，求序列中两个不同位置数a，b的和恰好等于M，
输出所有满足条件的方案。

//最直接的想法  O(n^2)
for( int i = 0;i < n; i++ ){
   for(int j = i+1; j < n; j++){
       if(a[i] + a[j] == M) printf("%d %d\n",a[i],a[j]);
    }
}

//two pointers做法  O(n)
#include<iostream>
using namespace std;
//i表示数组的第一个元素  j表示最后一个  res为两数相加需要等于的值
void twoPointers(int a[],int i,int j,int res){
    while(i<j){
        if(a[i]+a[j]==res){
            cout<<a[i]<<"+"<<a[j]<<"="<<res<<endl;
            i++; j--;
        }else if(a[i]+a[j]<res){
            i++;
        }else{
           j--;
        }
    }
}

int main(){
    int a[]={1,2,3,4,5,6};
    twoPointers(a,0,(sizeof a/sizeof a[0])-1,8);

    return 0;
}


//序列合并。  假设有两个**递增**序列A、B，要求将它们合并为一个**递增**序列
#include<iostream>
using namespace std;
// lena 表示a的长度 lenb表b的长度  
void hebing(int a[],int b[],int lena,int lenb){
    //i为a数组的下标  j为b数组的下标  temp为res数组的下标 res为合并之后的数组
    int i=0,j=0,temp=0,res[20]={0};
    /*
        如果a[i]<=b[j]  如果a[i]小于b[j] 就先将a[i]放进res数组中  然后将i+1(即指向a数组中的下一位)
                        如果相等的话 将a[i]、b[j]中的任意一个放入 (下面统一将a[i]放入)
        如果a[i]>b[j]  将b[j]放入 之后j+1
        假如任意一个数组的数全部都放完了的话就退出循环
    */
    while(i<lena&j<lenb){
        if(a[i]<=b[j]){
            res[temp++]=a[i++];
        }else{
            res[temp++]=b[j++];
        }
    }

    //将剩下没有放完的数组的数 直接放进去
    while(i<lena) res[temp++]=a[i++];
    while(j<lenb) res[temp++]=b[j++];
    for(int k=0;k<temp;k++){
        cout<<res[k]<<" ";
    }
}

int main(){
    int a[]={2,3,5,6,11,15,20};
    int b[]={1,2,6,7,9,12,65};
//    int res[100]={0};
    hebing(a,b,sizeof a/sizeof a[0],sizeof b/sizeof b[0]);
    return 0;
}