题目的大概意思是：快速找出在一个数组内的两个数，让这两个数之和等于一个给定的值。书中给出的解法三觉得应该是(NlogN）复杂度中比较快的，但这种解法为什么完备还要仔细推导一下才知道。因为是找两个数之和，解法二还可以再优化。排序后可以把数组分成两段，以和的一半作为分割点，这样就在二分查找时只需找出前半部分的Sum-arr[i]是否在后半部分中。我用SLT的binary_search实现了一下，但是此法由于排序，只能返回具体的解，如果返回解在原数组中的位置，那要复杂得多。
//给定条件为SUM()=10 #include<iostream> using namespace std; #include<vector> #include<algorithm> const int maxN=1000; int solv=0; class list { private: vector<int> v; int n; vector<int>::iterator cutPoint; public: list(int a[],int n1) { n=n1; for(int i=0;i<n;i++) v.push_back(a[i]); } //获得分割点 void GetCutPoint() { sort(v.begin(),v.end()); cutPoint=v.begin(); for(vector<int>::iterator it=v.begin();it!=v.end();it++) { if(*it>=5) { cutPoint=++it; break; } } } bool search ( ) { for(vector<int>::iterator it=v.begin();it!=cutPoint;it++) { int val=10-*it; bool result=binary_search(cutPoint,v.end(),val); if(result) { solv=val; return true; } } return false; } }; int main() { int a[]={5,6,7,4,7,9,8}; list list1(a,7); list1.GetCutPoint(); if(list1.search()) { cout<<"find it:"<<solv<<" "<<10-solv<<endl; } else { cout<<"not find"<<endl; } system("pause"); return 1; }
