查找具有给定总和的三元组 [英] finding a triplet having a given sum

问题描述

一段时间以来，我一直在努力解决这个问题。问题是这样的：-

I have been struggling with this questions for sometime now. The question goes like this:-

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

We have n^2 numbers. We need to find out if there exists a triplet a,b,c such that a+b+c = 0. For a more generic case, a+b+c = k. (k is given)

存在一个O（n ^ 2log（n））复杂度的解决方案。

There exists a solution with O(n^2log(n)) complexity.

任何帮助将不胜感激。

谢谢

推荐答案

要在O（n²logn）中获得此密码，您必须对数字进行排序。查找2个数字的所有组合，然后进行二进制搜索以查找第三个数字。

To get this in O(n²logn), you'd have to sort the numbers. Find all combinations of 2 numbers, and do a binary search to find the third.

问题的一般版本的上限更高。

The upper bound is much higher for the general version of the problem.

这篇关于查找具有给定总和的三元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！