找出数组a[]中符合a[i]+a[j]=K的数对

http://blog.csdn.net/jeanphorn/article/details/46564589

1.问题描述

在一个整数数组中，元素都为整数，没有重复数。设计一个算法找出满足两个数的和等于k值得数对。例如a[]={1,3,8,6,4}中两个数的和为7的数对为（1，6）和（3，4）。

2. 解决方案

2.1 暴力法

首先先到的可能就是暴力法，暴力没举出所有的数对然后再判对他们的和是否为K，但这种方法的时间复杂度为O（n^2），效率比较低，一般不可取。代码也就不写了。、

2.2 二分法

先对数组进行排序，然后使用二分查找算法，使用两个指针分片指向第一个和最后一个元素，然后从两端同时向中间遍历。

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;

}

2.2 hash方法

将数组存在hash表中，对每一个数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;//相同数对只取一次return1;}