Leetcode15. 三数之和

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

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

题解：
排序+双指针
1.给数组按照升序排序；
2.排序后固定一个数 $nums[i]$，

• 2.1.如果$nums[i]$大于 0，则三数之和必然无法等于 $0$，结束循环；
• 2.2.如果 $nums[i]$== $nums[i-1]$，则说明该数字重复，会导致结果重复，所以跳过本次循环；
• 2.3.使用左右指针指向 $nums[i]$后面的两端，数字分别为 $nums[j]$和 $nums[k]$，计算三个数的和 $sum$ 判断是否满足为 $0$，满足则添加进结果集;
  2.3.1.当 $sum == 0$ 时，$nums[j] == nums[j+1]$则会导致结果重复，应该跳过，j=j+1
  2.3.2当 $sum == 0$ 时，$nums[k] == nums[k−1]$ 则会导致结果重复，应该跳过，k = k-1
• 2.4.如果$sum>0$,则将后一位往前移动，即：$k = k-1$
• 2.5.如果$sum<0$,则将前一位往后移动，即：$j = j+1$

scala代码：

/**** @param nums* @return*/def threeSum(nums: Array[Int]): List[List[Int]] = {if (nums.length < 3) {null} else {val list = new ListBuffer[ListBuffer[Int]]()val nums1 = nums.sortedvar flag = truefor (i <- 0 until nums1.length; if (flag)) {if (nums1(i) > 0) {flag = false}breakable {//如果当前的值和上一个值相同，跳出本次循环,去重if (i > 0 && nums1(i) == nums1(i - 1)) {break()}//双指针j,kvar j = i + 1var k = nums1.length - 1val target = -nums1(i)while (j < k) {if (nums1(j) + nums1(k) == target) {val curr = new ListBuffer[Int]()curr.append(nums1(i))curr.append(nums1(j))curr.append(nums1(k))list.append(curr)k = k - 1//当左右两个值相等，去重while (j < nums1.length && nums1(j) == nums1(j - 1)) j = j + 1while (k > j && nums1(k) == nums1(k + 1)) k = k - 1} else if (nums1(j) + nums1(k) > target) {k = k - 1} else {j = j + 1}}}}val result: List[List[Int]] = list.map(_.toList).toListresult}}