一个无序数组,任意两个数相加等于一个给定的数,并且用复杂度最小的方法得出

Question

一个无序数组,任意两个数相加等于一个给定的数,并且用复杂度最小的方法得出

Answer 1

1.最简单的方法就是穷举,这种虽然简单,但是非常不划算,时间复杂度达到O(N^2)
2.可以换一个角度考虑,给定的数如果是M,那么针对数组中一个数字N,我们只需要查找一下数
组中是否含有M-N就可以了,这样就转换为数组查找问题了,然后可以利用空间换时间来搞
定,搞一个hash表,然后把每一个都映射到hash表中去,然后查找的时候就需要O(1)就可以
了,只不过空间复杂度达到O(N)
3.可以先排序一下,使用快排,时间复杂度为O(NlogN),然后令i = 0,j = n - 1,计算sum = arr[i]
+ arr[j],如果sum大于M就让j = j - 1,否则让i = i + 1,这样一轮下来就可以了,时间复杂度
O(N),总的时间复杂度为O(NlogN)