3 Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array

S = [-1, 0, 1, 2, -1, -4]

A solution set is:

[ [-1, 0, 1], [-1, -1, 2] ]

Scala

def threeSum(nums: Array[Int]):List[(Int,Int,Int)] = {
  scala.util.Sorting.quickSort(nums)
  var i,j,k,target: Int = 0
  j = nums.length - 1
  var ret = List[(Int,Int,Int)]()
  for (i <- 0 until nums.length) {
    k = i + 1
    j = nums.length - 1
    target = 0 - nums(i)
    while (k < j) {
      nums(j) + nums(k) match {
        case n if n == target => {
          ret = Tuple3(nums(i),nums(k),nums(j)) :: ret
          while (k < j && nums(k) == nums(k+1)) k += 1
          while (k < j && nums(j) == nums(j-1)) j -= 1
          j -= 1
          k += 1
        }
        case n if n > target => j -= 1
        case n if n < target => k += 1
      }
    }
  }
  ret
}

threeSum(Array(0,-1,2,3,4,5,6,1))

Second Tab