如何找到如果在一组大小N 3个数字恰好综上所述至M [英] How to find if 3 numbers in a set of size N exactly sum up to M

问题描述

我想知道我怎么能实现比O（N ^ 3）一个更好的解决方案。它类似背包和子集的问题。在我的问题N'LT = 8000，所以我就开始计算对数字的款项，并将它们存储在数组中。然后，我会为每个（M-总和[I]）的价值，但问题的有序集合二进制搜索，我还是会如何跟踪它总结归纳了指数[I]的。我知道我可以宣布额外的空间，但我和的阵列已经拥有了6400万的大小，所以我不能完成我的O（N ^ 2）的解决方案。请指教，如果我可以做一些优化，或者如果我需要一些完全不同的技术。

I want to know how I can implement a better solution than O(N^3). Its similar to the knapsack and subset problems. In my question N<=8000, so i started computing sums of pairs of numbers and stored them in an array. Then I would binary search in the sorted set for each (M-sum[i]) value but the problem arises how will I keep track of the indices which summed up to sum[i]. I know I could declare extra space but my Sums array already has a size of 64 million, and hence I couldn't complete my O(N^2) solution. Please advice if I can do some optimization or if I need some totally different technique.

推荐答案

您可以受益于一些通用的技巧，以提高你的算法的性能。

You could benefit from some generic tricks to improve the performance of your algorithm.

1）不要将你用什么只有一次

1) Don't store what you use only once

这是一个常见的​​错误，以存储更多的比你真正需要的。每当你的内存需求似乎炸毁的第一个问题要问自己是的我是否真的需要存储的东西？的这证明，你不这样做（如史蒂夫注释中解释），计算总和两个数字的（在一个三角形的方式，以避免重复自己），然后再检查的第三个了presence。

It is a common error to store more than you really need. Whenever your memory requirement seem to blow up the first question to ask yourself is Do I really need to store that stuff ? Here it turns out that you do not (as Steve explained in comments), compute the sum of two numbers (in a triangular fashion to avoid repeating yourself) and then check for the presence of the third one.

我们丢弃O（N ** 2）记忆复杂！目前预计的内存为O（N）。

We drop the O(N**2) memory complexity! Now expected memory is O(N).

2）了解你的数据结构，特别是：哈希表

2) Know your data structures, and in particular: the hash table

完美的哈希表很少（如果有的话）来实现，但它是（理论上）可能的手艺哈希表为O（1）插入，查询和删除的特性，并在实践中你做接近那些复杂的（艰难的，但是通常还是在一个较高的常数因子的成本，这将使你preFER所谓的次优的方法）。

Perfect hash tables are rarely (if ever) implemented, but it is (in theory) possible to craft hash tables with O(1) insertion, check and deletion characteristics, and in practice you do approach those complexities (tough it generally comes at the cost of a high constant factor that will make you prefer so-called suboptimal approaches).

因此​​，除非你需要订购（出于某种原因），会员更是通过一般的哈希表进行测试。

Therefore, unless you need ordering (for some reason), membership is better tested through a hash table in general.

我们放下登录N'一词在速度上的复杂性。

We drop the 'log N' term in the speed complexity.

通过这两项建议你轻松搞定是你所要求的：

With those two recommendations you easily get what you were asking for:

1. 在构建一个简单的哈希表：数量是关键，卫星数据相关联的指数
2. 在迭代三角形的方式对您的数据集：因为我在[0..N-1];对于j在[1 + 1 ... N-1]
3. 在每次迭代中，检查 K = M - 设置[I] - 设置[J] 是哈希表中，如果是，提取物 K =表[K] 和如果 K！=我和 K！= j的 的存储三重（I，J，K）在你的结果。

1. Build a simple hash table: the number is the key, the index the satellite data associated
2. Iterate in triangle fashion over your data set: for i in [0..N-1]; for j in [i+1..N-1]
3. At each iteration, check if K = M - set[i] - set[j] is in the hash table, if it is, extract k = table[K] and if k != i and k != j store the triple (i,j,k) in your result.

如果一个单一的结果就足够了，你可以只要你得到的第一个结果停止迭代，否则你只是存储所有的三倍。

If a single result is sufficient, you can stop iterating as soon as you get the first result, otherwise you just store all the triples.

这篇关于如何找到如果在一组大小N 3个数字恰好综上所述至M的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！