寻找三元组并使其和为给定值

Question

我已经苦苦思考这个问题有一段时间了。问题是这样的：-

我们有n^2个数字。我们需要找出是否存在一个三元组a，b，c，使得a+b+c = 0。对于更一般的情况，a+b+c = k。（给定k）

有一个O(n^2log(n))复杂度的解决方案。

任何帮助将不胜感激。

谢谢

- Pigol

---

你可能想阅读现有的文献，了解子集和问题的更一般版本，这是你所提出的问题的更广泛的版本。http://en.wikipedia.org/wiki/Subset_sum_problem - mqp

只是出于好奇，这是为欧拉计划而做的吗？ - Carl Smotricz

n^2个数字是什么意思？n是什么？ - MAK

n的平方等于square(n)，其中数字可能是唯一的。 - Pigol

你的答案在这里：https://dev59.com/_HI95IYBdhLWcg3w-DDz - Steve

Answer 1

要在O(n²logn)的时间复杂度内完成此操作，您需要对数字进行排序。找到所有两个数字的组合，并进行二分查找以找到第三个数字。

对于问题的一般版本，上限要高得多。

- Anurag

---

组合的数量将会是O(n^4)。我们正在寻找一种优化的解决方案。 - Pigol

所以基本上，重新表述一下，你的意思是有n个项目，并且有一个O(nlog√n)的解决方案？ - Anurag

@Anurag，来吧，log√n等于½log n。 - P Shved

好的，Pavel，所以它是O(nlogn)的..我还在为选择Unicode字符而欢欣鼓舞呢 :) - Anurag

Answer 2

我写了一个初步的解决方案。

它绝对可以在O(n^2)内完成。 你不需要对其进行排序。

这是一个需要将两个数字求和为x的问题的扩展，诀窍是使用哈希表。

def triplets(l, total):
    """Sum of 3 numbers to get to total 
    Basically an extension of the 2 table 
    """
    l = set( l)
    d = { }

    for i in l:
        remain = total - i

        inside = {}
        for j in l:
            if i == j:
                continue
            inside[j] = remain -j

        d[i] = inside

    good = set()

    for first, dic in d.iteritems():
        for second, third in dic.iteritems():
            if third in l:
                good.add( tuple(sorted([first, second, third])) )

    for each in good: 
        print each

triplets( [2, 3, 4, 5, 6], 3+4+5)

注意：我们可以使用一种快速排序方法来处理三元组，其时间复杂度为O(1)。

- xjq233p_1

---

请提供您的解决方案的C或Java代码，可以吗？ - Hengameh