Best complexity to find solutions to $x^2+y^2=z^2$
I think you are asking about Pythagorean Triples (the form $x^2+y^2=z^2$ where $x$,$y$ and $z$ are integers).

Euclids Formula is generally thought to be efficient for finding primitive Pythagorean Triples.You can multiply these primitive triples with a constant to get non primitive Pythagorean Triples.

Here are some other methods of finding Pythagorean Triples