objective-c - 如何编写客观的 C 代码来检查数组/列表中任意三个数字的总和是否与给定数字匹配？

Question

可能重复：
在数组中查找三个元素的总和最接近给定数字

如何编写 Objective C 代码来检查数组/列表中任意三个数字的总和是否与给定数字匹配？

Answer 1

第 1 步：排序，O(nlgn)

第2步：迭代每个数字，比如A，（这花费O（n）），然后检查任何两个数字的总和是否等于给定数字减去A（这是一个花费O（n）的经典问题）

总复杂度：O(n^2)

Answer 2

这是另一种方式

X,Y,Z 是数组的索引，并且 P 被赋予 Number 。

如果条件是 X+Y=P，那么我们对数组进行排序，然后我们选择每个元素，然后在剩余的数组中搜索 PY。如果搜索成功，那么很好，否则返回 False。

所以搜索需要 log(n) time(binary search) 所以对于 n 个元素它需要 O(nlog(n)) time 。

现在我们的条件是 X+Y+Z=P 我们推导出来 X+Y=PZ

Now Pick a number Z and calculate P-Z and let it be R . 
Now the problem is deduce to X+Y=R .So time complexity is O(nlog(n))
Since R varies n times for n picks in array so complexity is O((N^2)log(n))) .

Answer 3

这是 Python 中的一个蛮力解决方案，其价值仅在于其简洁性，而不在于其效率：

import itertools
def anyThreeEqualTo(list, value):
    return any([sum(c) == value for c in itertools.combinations(list, 3)])

另一个想法：

import itertools
def anyThreeEqualTo(list, value):
    for c in itertools.combinations(list, 3)])
        if sum(c) == value:
            return True
    return False

这些解决方案依次尝试每个三元组，直到找到具有所需总和的一个。