The Code is in Scala.
/**
* O(n^2) solution to find out if and which 3 of them add up to 0
*
*/
object FindThreeNumbersSumToZero {
def sort(arr:Array[Int]): Array[Int] =
if (arr.length<2) arr
else {
val pivot = arr (arr.length / 2)
sort (arr filter (pivot>)) ++
(arr filter (pivot == )) ++ sort (arr filter(pivot <))
}
def findThreeNumbersAddedToZero (arr: Array[Int]) : (Int, Int, Int) = {
val a : Array[Int] = sort(arr);
for(i <- 0 until a.length) {
var iter = i+1;
var reviter = a.length-1;
while (iter < reviter) {
var v = a(i) + a(iter) + a(reviter);
if (v==0)
return (a(i), a(iter), a(reviter));
else if (v<0)
iter = iter + 1;
else
reviter = reviter-1;
}
}
return null;
}
def main(args: Array[String]) {
val arr = Array(-11, 19, -2, 22, -4, 4, 10, 6, 12, 23)
val tuple = findThreeNumbersAddedToZero (arr);
println("array is [" + arr.mkString(" ") + "] ");
println("tuple is " + tuple + "");
}
}
Enjoy the journey.