Question

iOS一个数组中求出任意几个数的和等于给定数

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)