4 Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?

Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array

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

and

target = 0

A solution set is:

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

Scala

import scala.util.Sorting.quickSort

def fourSum(nums: Array[Int], target: Int):List[(Int,Int,Int,Int)] = {
  quickSort(nums)
  var ret:List[(Int,Int,Int,Int)] = Nil
  for (i <- 0 until nums.length) {
    for (j <- i + 1 until nums.length) {
      // fixed first two indexes
      var (k,l) = (j + 1, nums.length - 1)
      while (k < l) {
        nums(i)+nums(j)+nums(k)+nums(l) match {
          case sum if sum == target => {
            val tup = (nums(i),nums(j),nums(k),nums(l))
            // check duplicate
            if (ret.isEmpty || tup != ret.head) {
              ret = tup :: ret
            }
            l -= 1
            k += 1
          }
          case sum if sum > target => l -= 1
          case sum if sum < target => k += 1
        }
      }
    }
  }
  ret
}

fourSum(Array(1, 0, -1, -1, 0, -2, 2), 0)

Second Tab