How to find pythagorean triplets in an array faster than O(N^2)?
- by SS
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(n2).
Pythagorean triplet is a set {a,b,c} such that a2 = b2 + c2. 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}.