如何找到在一个数组毕达哥拉斯三胞胎快于O（N ^ 2）？ [英] How to find pythagorean triplets in an array faster than O(N^2)?

问题描述

有人建议了一种算法，发现在一个给定的数字阵列中的所有毕达哥拉斯三胞胎？如果可能的话，请提出的算法为O快（N ² ）。

Can someone suggest an algorithm that finds all Pythagorean triplets among numbers in a given array? If it's possible, please, suggest an algorithm faster than O(n²).

毕达哥拉斯三重的是一组{A，B，C}使得 ² = B ² + C ² 。示例：数组 [9，2，3，4，8，5，6，10] 算法的输出应为 {3， 4，5} 和 {6，8，10} 。

Pythagorean triplet is a set {a,b,c} such that a² = b² + c². Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}.

推荐答案

我理解这个问题，因为

给定一个数组，找到所有三胞胎我，Ĵ和 K ，使得[I] ² = A [J] ² + A [K] ²

Given an array, find all such triplets i,j and k, such that a[i]² = a[j]²+a[k]²

该解决方案的核心思想是：

The key idea of the solution is:

• 广场的每个元素。 （这需要O（n）的时间）。这将减少原始任务发现在阵列三个数字，其中一个是另两个的总和。

• Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".

现在你知道如何解决这样的任务，在不到为O（n ² ）时，使用这种算法。在我心里来，无非以下为O（n ² ）解决方案：

Now it you know how to solve such task in less than O(n²) time, use such algorithm. Out of my mind comes only the following O(n²) solution:

1. 以升序排序的数组。这需要为O（n log n）的。

2. 现在考虑每个元素[1]。如果A [1] = A [J] + A [K]，然后，因为数字是积极的，阵列现在排序，K＆LT; i和j＆LT;我。

1. Sort the array in ascending order. This takes O(n log n).

2. Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i.

要找到这样的指标，运行一个循环，增加Ĵ从 1 到我，并降低 K 从我到 0 在同一时间，直到他们满足。增加Ĵ如果 A [J] + A [K]＆LT; A [1] ，并减少 K 如果总和大于 A [1] 。如果该和是相等的，这是其中一个答案，打印，和移位两个索引

To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes.

这需要O（I）业务。

这篇关于如何找到在一个数组毕达哥拉斯三胞胎快于O（N ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！