Pythagorean triples solution

First, square each element of the array. Then insert every pair of elements in the array into a hash table, using their sum as the hash code. This step is O(n²). Now, we can easily (O(n) time) test if any element in the array is the sum of a pair of elements by looking up that element in the hash table. These three elements form a Pythagorean triple.

I have seen an alternative O(n^2) solution without using hashtables:

1) square the elements, and sort the values: O(n log n), keep the original indices using extra memory
2) traverse through the sorted array, for each element s[i], set two pointers initially at s[i+1] and s[n], and move them accordingly until a good triplet is found or the pointers meet: O(n * n)

some more thoughts:

Actually according the problem definition, there are also extreme situations where > O(n^2) operations will be needed - e.g. all the elements are 0, in which case we need at least n*(n-1)*(n-2) to enumerate all the a^2+b^2=c^2 combinations.