检查给定整数是否等于整数数组两个元素之和的最佳算法是什么？

Question

def check_set(S, k):    
S2 = k - S
set_from_S2=set(S2.flatten())
for x in S:    
    if(x in set_from_S2):    
        return True
return False

我有一个给定的整数k，我想检查k是否等于数组S的两个元素的和

S = np.array([1,2,3,4])
k = 8

在这种情况下，它应该返回False，因为S中没有两个元素的和为8。上面的代码类似于8 = 4 + 4，因此它返回True

我找不到一个复杂度为O(n)的算法来解决这个问题。你知道吗

有人能帮我吗？你知道吗

Answer 1

再加上MBo的答案。你知道吗

“最优”在算法方面可能是一个模棱两可的术语，因为在算法运行速度和内存效率之间常常存在折衷。有时我们也可能对最坏情况下的资源消耗或平均资源消耗感兴趣。我们将在这里循环最坏的情况，因为它更简单，大致相当于我们场景中的平均值。你知道吗

让我们调用n数组的长度，并考虑3个示例。你知道吗

例1

对于我们的问题，我们从一个非常简单的算法开始，使用两个嵌套循环在数组上迭代，并检查每两个不同索引项的总和是否达到目标数。你知道吗

• 时间复杂性：最坏情况下（答案是False或True但我们在最后一对检查项上找到它）有n^2循环迭代。如果您熟悉big-O表示法，我们会说算法的时间复杂度是O(n^2)，这基本上意味着就我们的输入大小而言n，求解算法所需的时间或多或少会像n^2一样随乘因子增长（好吧，从技术上讲，这个符号的意思是“最多像n^2加上一个乘法因子，但是用“或多或少像”来代替它是对语言的一种普遍滥用。

• 空间复杂性（内存消耗）：我们只存储一个数组，加上一组固定的对象，这些对象的大小不依赖于n（Python需要运行的所有东西，调用堆栈，可能是两个迭代器和/或一些临时变量）。因此，内存消耗随n增长的部分只是数组的大小，即n乘以在数组中存储整数所需的内存量（我们称之为sizeof(int)）。

结论：时间是O(n^2)，记忆是n*sizeof(int)（+O(1)，也就是说，到了一个额外的常数因子，这对我们来说无关紧要，从现在起我们将忽略它）。你知道吗

例2

让我们考虑一下MBo答案中的算法。你知道吗

• 时间复杂度：比例1要好得多。我们从创建字典开始。这是在n上的循环中完成的。在适当的条件下，在字典中设置键是一个常数时间操作，因此第一个循环的每个步骤所花费的时间不依赖于n。因此，现在我们在时间复杂性方面使用了O(n)。现在我们在n上只剩下一个循环。访问字典中的元素所花费的时间与n无关，因此总的复杂性也是O(n)。将我们的两个循环组合在一起，因为它们都像n一样增长到一个乘法因子，所以它们的和（到另一个乘法因子）也是如此。总计：O(n)。

• 内存：基本上和以前一样，加上n元素的字典。为了简单起见，让我们考虑一下这些元素是整数（我们可以使用布尔），并且忘记字典的一些方面，只计算用于存储键和值的大小。有n个整型键和n个整数值要存储，它们在内存方面使用2*n*sizeof(int)。再加上之前的数据，我们总共有3*n*sizeof(int)。

结论：时间是O(n)，记忆是3*n*sizeof(int)。当n增长时，该算法的速度相当快，但使用的内存是示例1的三倍。在一些几乎没有可用内存的奇怪场景中（可能是嵌入式系统），这个3*n*sizeof(int)可能太多了，而且您可能无法使用这个算法（无可否认，这可能永远不会是一个真正的问题）。你知道吗

例3

我们能在例1和例2之间找到一个折衷点吗？你知道吗

一种方法是复制与示例1相同的嵌套循环结构，但是一些预处理以更快的速度替换内部循环。为此，我们对初始数组进行排序。使用well-chosen algorithms完成，时间复杂度为O(n*log(n))，内存使用可以忽略不计。你知道吗

一旦我们对数组进行了排序，我们就编写外循环（它是整个数组上的一个常规循环），然后在外循环中，使用二分法搜索我们缺少的数字以到达目标k。这种二分法的内存消耗为O(log(n))，其时间复杂度也为O(log(n))。你知道吗

• 时间复杂度：预处理排序为O(n*log(n))。然后在算法的主要部分，我们有n调用O(log(n))二分法搜索，总计O(n*log(n))。所以，总的来说，O(n*log(n))。

• 内存：忽略常量部分，我们有数组的内存（n*sizeof(int)）和二分法搜索中调用堆栈的内存（O(log(n))）。总计：n*sizeof(int) + O(log(n))。

结论：时间是O(n*log(n))，记忆是n*sizeof(int) + O(log(n))。内存几乎和示例1一样小。时间复杂度略高于示例2中的时间复杂度。在由于缺少内存而无法使用示例2的场景中，就速度而言，下一个最好的例子是示例3，它几乎与示例2一样快，如果非常慢的示例1运行，它可能有足够的空间运行。你知道吗

总体结论

这个答案只是为了说明“最优”在算法中是上下文相关的。在这个特定的例子中，我们不太可能选择实现例子3。一般来说，如果n太小，人们会选择最简单的设计和最快的代码，那么您会看到示例1；如果n稍微大一点，我们需要速度，那么您会看到示例2。但是如果你看看我链接的维基百科页面，你会发现没有一个算法在任何方面都是最好的。他们都有可能被更好的东西取代。你知道吗

Answer 2

您必须考虑同一项目的多个实例，因此在这里设置不是一个好的选择。你知道吗

相反，您可以使用value_field = number_of_keys（作为变量-from collections import Counter）利用字典

A = [3,1,2,3,4]
Cntr = {}
for x in A:
    if x in Cntr:
        Cntr[x] += 1
    else:
        Cntr[x] = 1

#k = 11
k = 8
ans = False
for x in A:
    if (k-x) in Cntr:
        if k == 2 * x:
            if Cntr[k-x] > 1:
                ans = True
                break
        else:
            ans = True
            break
print(ans)

对于k=5,6返回True（我又加了一个3），对于k=8,11返回False