Finding all Pythagorean triples in an array

An obvious solution to this problem could be examine all possible triples in the array and check if it satisfies the above property.
But this solution takes O(n³) time.

We can do better than this if we first square all the elements and sort them in descending order.

Then this problem is simplified to finding three indices in the array i,j,k such that arr[i] = arr[j]+arr[k]

The algorithm is as follows.

For each array[i] 0 <= i < n-2
     index1 <- i+1
     index2 <- n-1
            
     While index1 < index 2
                 
        If array[i] = array[index1] + array[inde2]
           Print Triple
           index1++
           index2–
        If array[i] <  array[index1] + array[inde2]
           index1++
        Otherwise
           index2–

Here is the implementation of the above in C++. It takes O(n log n) for sorting and O(n²) for the actual algorithm. So the effective time complexity for this problem is O(n²)

Solution 2:
Alternatively you can use a Hash set to store all the square values. Then examine all possible pairs in the array to check if sum of their squares exists in the set.
This approach also takes O(n²) time but uses O(n) extra space. 
Note: The hash_set implementation is available only in Visual studio 10 compiler and above. In C++ 11 standard it is mentioned as unordered_set. If we use normal set, the time complexity will become O(n² log n).