找出数组中和为N的所有配对

有一个集合a，里面有n个正整数，乱序排列。给定一个正整数N，求，a中任意两个数相加等于N，共有哪些种组合情况。例如，集合为{1,3,44,2,4,5,54,222,368}  N=6,则结果集为{1,5}，{2,4}

我的思路，

1. 用N减去每个元素得到另一个数组b，嵌套循环找到a与b中值相同而位置不同的元素对；空间复杂度2N，时间复杂度O(N^2)。


2. 将a按照升序排序，初始化变量max_loc=N-1，从最小值a[i=0]开始遍历，
    a. 若max_loc<=i，结束程序，否则进入b；
    b. 判断a[max_loc] + a[i]与N大小关系；<N则continue对a[i]的遍历；=N则输出这对数，max_loc--，继续b；>N则max_loc--，继续b；
    该方法的空间复杂度是1，时间复杂度是O(NlgN+N)，证明如下：
    排序的复杂度视为NlgN，后面配对的部分复杂一点，循环第i个值的复杂度用f(i)表示，有如下的关系，f(0)<N，f(1)<N-f(0)，这是因为a[0]遍历走过的那部分最大值不需要在a[1]的循环里再去检验了，所以有f(i)<N-[f(0)+...+f(i-1)]，进而得到f(0)+f(1)+...+f(N-1)<N，所以说整个算法的复杂度是O(NlgN+N)。

欢迎讨论和拍砖！！

评论

2 楼 peizhyi 2013-06-03  

sydongda 写道

有没有考虑重复的数字

不好意思，好久没回来看博客。
的确没有考虑重复数的情况，应该在b里修改下，如果=N，继续遍历，大于N才max_loc--。
谢谢关注！欢迎一起讨论！

1 楼 sydongda 2012-07-23  

有没有考虑重复的数字