Pythagorean triplets

Someone asked me a question(asked to him in an interview) that how to开发者_JAVA百科 find triplets in an integer array A[] which satisfy following condition:

a[i]^2 + a[j]^2 = a[k]^2

i have done it in o(n^2 logn) can it be optimized.

A variation of your approach that's O(n^2).

def findPythagoreanTriplets(array):
  array = sorted(array)
  for i in range(len(array)):
    k = i + 2
    for j in range(i + 1, len(array)):
      while k < len(array) and (array[k] ** 2 < (array[i] ** 2 + array[j] ** 2)):
        k += 1
      if k < len(array) and (array[k] ** 2 == (array[i] ** 2 + array[j] ** 2)):
        print "%d^2 + %d^2 = %d^2" % (array[i], array[j], array[k])

This is Python code, but converting to C shouldn't be hard. (Actually, this question seems language agnostic, so I'm not sure why you've got the c tag...)

This is assuming all of the inputs are non-negative. You could probably make it work for negative integers as well, but you'd need to sort by the squared value, not by the input value (for non-negative numbers they're the equivalent).

Instead of doing a binary search you just do a linear search for k, but you can pick up from where the previous j's search left off, so searching for k is "free".

At least you can use hash table to store squares. So search of (i^2+j^2) for each pair will be in O(1) and in overall algorithm will take O(n^2)