C++ 对一个巨大的数组执行计算

Question

我在面试时被问到一个问题，但我不知道正确答案....

问题是:

如果您有一个包含 1 到 100 之间的 10 000 000 个整数的数组，请(有效地)确定这些整数中有多少对总和等于或小于 150。

如果没有循环中的循环，我不知道如何做到这一点，但这不是很有效。

有没有人给我一些指点？

Answer 1

一种方法是创建一个包含 100 个元素的较小数组。遍历 10,000,000 个元素并计算每个元素的数量。将计数器存储在 100 元素数组中。

    // create an array counter of 101 elements and set every element to 0
    for (int i = 0; i < 10000000; i++) {
          counter[input[i]]++;
    }

然后执行从 1 到 100 的第二个循环 j。在其中，有一个从 1 到 min(150-j,j) 的循环 k。如果 k!=j，添加 counter[j]*counter[k]。如果 k=j，添加 (counter[j]-1)*counter[j]。

总和就是你的结果。

您的总运行时间上限为 10,000,000 + 100*100 = 10,010,000(实际上小于此值)。

这比 (10,000,000)^2 快很多，即 100,000,000,000,000。

当然要让出101 int内存空间。

完成后删除计数器。

另请注意(正如在下面的讨论中所指出的)这是假设顺序很重要。如果顺序无关紧要，只需将结果除以 2。