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.sorted
var flag = true
for (i <- 0 until nums1.length; if (flag)) {
if (nums1(i) > 0) {
flag = false
}
breakable {
//如果当前的值和上一个值相同,跳出本次循环,去重
if (i > 0 && nums1(i) == nums1(i - 1)) {
break()
}
//双指针j,k
var j = i + 1
var k = nums1.length - 1
val 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 + 1
while (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).toList
result
}
}