休息时间，发现任何三联其中O型匹配毕达哥拉斯式（N ^ 2） [英] Break time, find any triple which matches pythagoras equation in O(n^2)

问题描述

我认为这是有趣的解决这个节日：

I think it's interesting to solve this in holiday:

由于 N 整数，所有的人都在 1..1 ^ 3 ，发现如果有三这为O匹配毕达哥拉斯式（N ^ 2）。

Given n integers, all of them within 1..n^3, find if there is a triple which matches pythagoras equation in O(n^2).

正如你所知道的毕达哥拉斯方程为 A ^ 2 + B ^ 2 = C ^ 2 。例如： 3 ^ 2 + 4 ^ 2 = 5 ^ 2 。

As you know pythagoras equation is a^2 + b^2 = c^2. for example 3^2 + 4^2 = 5^2.

正如你所知道为O（n ^ 2 log n）的简单（一点点思想），但将有助于解决为O（n ^ 2）。 （空间并不重要）。

As you know O(n^2 log n) is easy (with a little thinking), but will help to solve O(n^2). (space is not important).

编辑：作为yi_H提供有查找表，可以很容易地解决这个问题，但更困难的，空间的限制是O（n ^ 2）

As yi_H offered there is lookup table which can solve this problem easily, but for making it harder, space limit is O(n^2).

推荐答案

为O（n ² ）时间，O（n）的空间：方形所有数组元素，排序，为每个Z阵列中使用经典线性时间算法以确定是否有在阵列中存在的x，y，使得X + Y = Z

O(n²) time, O(n) space: square all array elements, sort, for each z in the array use the classic linear-time algorithm to determine whether there exist x, y in the array such that x + y = z.

这篇关于休息时间，发现任何三联其中O型匹配毕达哥拉斯式（N ^ 2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！