从数字的给定数组找到所有的组的3个数字有总和值N [英] From the given array of numbers find all the of numbers in group of 3 with sum value N

问题描述

由于是数字的数组：

1, 2, 8, 6, 9, 0, 4

我们需要找到所有的号码组三其总结为一个值N（比方说11这个例子）。在这里，组三可能的数字是：

We need to find all the numbers in group of three which sums to a value N ( say 11 in this example). Here, the possible numbers in group of three are:

{1,2,8}, {1,4,6}, {0,2,9}

我能想到的第一个解决方案是为O（n ^ 3）。后来，我可以提高一点（N ^ 2 log n）的使用方法：

The first solution I could think was of O(n^3). Later I could improve a little(n^2 log n) with the approach:

1. Sort the array.
2. Select any two number and perform binary search for the third element.

是不是可以进一步与其他一些方法改善？

Can it be improved further with some other approaches?

推荐答案

您当然可以做到这一点在为O（n ^ 2）：为每个我阵列中，两个值测试是否总结为镍。

You can certainly do it in O(n^2): for each i in the array, test whether two other values sum to N-i.

您可以在 O（N）到 K在一个排序的数组总和两个值通过扫是否测试无论是在一次结束。如果两个元素你上的总和为太大，递减从右到左索引使其变小。如果该和过小，则增加左到右索引可以使更大。如果有一种可行的对，你会发现他们，你在执行大多数 2 * N 迭代你在一端或其他无路可走之前。您可能需要code不理你正在使用的我的价值，取决于规则是什么。

You can test in O(n) whether two values in a sorted array sum to k by sweeping from both ends at once. If the sum of the two elements you're on is too big, decrement the "right-to-left" index to make it smaller. If the sum is too small, increment the "left-to-right" index to make it bigger. If there's a pair that works, you'll find them, and you perform at most 2*n iterations before you run out of road at one end or the other. You might need code to ignore the value you're using as i, depends what the rules are.

你也可以使用某种形式的动态规划，从 N 工作下来，你可能最终会随着时间的推移像 O（N * N）左右。现实我不认为这是什么更好的：它看起来像所有的数字都是非负的，所以如果 N 比 N <大得多/ code>启动，然后才能在快速抛出任何大的值从阵列中，同时也超出了3份各值（或2份任何重复，只要你检查是否 3 *我==ñ放弃的第三个副本之前我）。这一步之后， N 是 O（N）。

You could instead use some kind of dynamic programming, working down from N, and you probably end up with time something like O(n*N) or so. Realistically I don't think that's any better: it looks like all your numbers are non-negative, so if n is much bigger than N then before you start you can quickly throw out any large values from the array, and also any duplicates beyond 3 copies of each value (or 2 copies, as long as you check whether 3*i == N before discarding the 3rd copy of i). After that step, n is O(N).

这篇关于从数字的给定数组找到所有的组的3个数字有总和值N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！