LeetCode.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

• 注意：答案中不可以包含重复的三元组。
• 示例：
  给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]

解法：

object ThreeNumSum {

     def main(args: Array[String]): Unit = {
          println(solution1(Array(-1, 0, 1, 2, -1, -4)))
          println(solution2(Array(-1, 0, 1, 2, -1, -4)))
          println(solution2(Array(0, 0, 0)))
     }

     /**
      * O(n^3)
      **/
     def solution1(nums: Array[Int]): List[List[Int]] = {
          val set = scala.collection.mutable.Set[List[Int]]()
          for (i <- 0 until nums.length) {
               for (j <- i + 1 until nums.length) {
                    for (k <- j + 1 until nums.length) {
                         if (nums(i) + nums(j) + nums(k) == 0) {
                              set += List(nums(i), nums(j), nums(k)).sortWith((a, b) => if (a - b < 0) true else false)
                         }
                    }
               }
          }
          set.toList
     }

     /**
      * 双指针时间复杂度O(n^2)，空间复杂度O(1)
      */
     def solution2(nums: Array[Int]): List[List[Int]] = {
          val set = scala.collection.mutable.Set[List[Int]]()
          util.Arrays.sort(nums)

          if (nums.length == 3 && nums(0) + nums(1) + nums(2) == 0) {
               return List(nums.toList)
          }

          for (i <- 0 until nums.length - 3) {
               var l = i + 1
               var r = nums.length - 1
               while (l < r) {
                    if (nums(l) + nums(r) > 0 - nums(i)) {
                         r -= 1
                    } else if (nums(l) + nums(r) < 0 - nums(i)) {
                         l += 1
                    } else if (l != r) {
                         set += List(nums(i), nums(l), nums(r)).sortWith((a, b) => if (a - b < 0) true else false)
                         l += 1
                    }
               }
          }

          set.toList
     }
}