http://blog.csdn.net/jeanphorn/article/details/46564589
1.問題描述
在一個整數(shù)數(shù)組中，元素都為整數(shù)，沒有重復數(shù)。設計一個算法找出滿足兩個數(shù)的和等于k值得數(shù)對。例如a[]={1,3,8,6,4}中兩個數(shù)的和為7的數(shù)對為（1，6）和（3，4）。
首先先到的可能就是暴力法，暴力沒舉出所有的數(shù)對然后再判對他們的和是否為K，但這種方法的時間復雜度為O（n^2），效率比較低，一般不可取。代碼也就不寫了。、
先對數(shù)組進行排序，然后使用二分查找算法，使用兩個指針分片指向第一個和最后一個元素，然后從兩端同時向中間遍歷。
1）、如果a[i] + a[j] > K; 則j–。
2）、如果a[i] + a[j] = K; 則i++,j–。
3）、如果a[i] + a[j] < K; 則i++。
代碼如下：
intFindCouple(inta[],intn,intk)
{
inti=0,j=n-1;sort(a,a+n);while(i < j)? ??
{
if(a[i] + a[j] == k)? ? ? ??
{
printf("(%d,%d)\n",a[i],a[j]);? ? ? ??
? ? i++;? ? ? ? ?
?? j--;? ? ??
? }
elseif(a[i] + a[j] > k) j--;
else
i++;? ? }
return 1;
}
將數(shù)組存在hash表中，對每一個數(shù)a[i]在hash表中查找K-a[i]是否存在。時間復雜度和空間復雜度都為O(n)。
intFindCouple_hash(inta[],intn,intk){mapmp;for(inti=0; i < n; i++)? ? ? ? mp[a[i]] =1;for(inti =0; i < n; i++)if(mp[k-a[i]] ==1)printf("(%d,%d)\n",a[i],k-a[i]),mp[a[i]]=0;//相同數(shù)對只取一次return1;}
