/*---------------------------------------------- find ,if any,two element in sorted A, whose sum is x in O(n) ---------------------------------------------*/bool FindSum(int A[],int n,int x,int &i,int &j){ i=0,j=1; //initialize left and right pointer
//find first i and j where A[i]+A[j]>x while((A[i]+A[j])<x&&j<n) { i++; j++; }
if(j>=n) //index out of bound return false; else if((A[i]+A[j])==x) //solution found return true;
//A[i]+A[j]>x i--; //left pointer backtrack while(i>=0&&j<n){ if((A[i]+A[j])==x) return true; //solution found else if((A[i]+A[j])>x) i--; //left pointer backtrack else j++; //right pointer advance}
return false;}
改进:若不是有序,则先对其排序O(nlogn)
