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.
No comments:
Post a Comment