腾讯&leetcode15：三数之和

[sisterAn]

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

注意： 答案中不可以包含重复的三元组。

示例：

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

附赠leetcode地址：leetcode

可结合 字节&leetcode1：两数之和 一起查看

[huangruitian]

//这道题经典的是细节，需要考虑蛮多细节的
//解法：
//1.暴力破解，三层枚举，O（n^3）效率太低不考虑
//2.a+b+c = 0，转换思路，a+b = -c，这不就是两数之和嘛？
//3.利用双指针夹逼，但是怎么避免重复呢？
//3.1 排序即可，利用排序好的数组，固定一个指针i，夹逼选举left和right
//3.2 这道题难度在于要考虑的细节太多，多想想即可。
//3.3 扩展一下，如果是4数之和，五数之和，N数之和呢？怎么解决？
const threeSum = (nums) => {
 const len = nums.length
 const result = []
 // 因为是三数之和，小于三个不用考虑了
 if(len < 3){
 return result
 }
 nums.sort((a, b) => a - b)
 // len - 2 同样道理，小于三个不用考虑
 for(let i = 0; i < len - 2; i++){
 // 如果第一个就大于0了，三个加起来肯定大于0
 if(nums[i] > 0){
 break
 }
 // 避免掉重复的情况
 if(i && nums[i] === nums[i - 1]){
 continue
 }
 let left = i + 1
 let right = len - 1
 // 双指针夹逼
 while(left < right){
 const sum = nums[i] + nums[left] + nums[right]
 if(sum === 0){
 result.push([nums[i], nums[left++], nums[right--]])
 // push 加了之后防止还存在重复
 while(nums[left] === nums[left - 1]){
 left++
 }
 while(nums[right] === nums[right + 1]){
 right--
 } 
 }else if(sum > 0){
 right--
 }else{
 left++
 }
 }
 }
 return result
}

[thxiami]

@huangruitian
1.双指针寻找两数之和的方法挺巧妙的~ 可以用二分法进一步加快一下紧逼速度
2. K数之和的问题, 目前的思路也是类似将三数之和降为两数之和的办法.
假设数组有 n 个数, 求满足 K 个数之和为sum的所有组合.
a. 利用O(nlogn) 的时间排序
b. 一个循环将问题拆分为 n 个(K-1)数之和, 时间复杂度为 T(K) = O(n * T(K-1)) = O(n^(k-1))

 // 双指针夹逼
 while(left < right){
 const sum = nums[i] + nums[left] + nums[right]
 if(sum === 0){
 result.push([nums[i], nums[left++], nums[right--]])
 // push 加了之后防止还存在重复
 while(nums[left] === nums[left - 1]){
 left++
 }
 while(nums[right] === nums[right + 1]){
 right--
 } 
 }else if(sum > 0){ 
 // 这里可以使用二分法进一步加快寻找符合条件的 right, 即 nums[right]= 0 - nums[i] - nums[left]
 // right--
 }else{ // 同理也可以用二分法加快逼近速度
 // left++
 }
 }
 }

[huangruitian]

right

@huangruitian
1.双指针寻找两数之和的方法挺巧妙的~ 可以用二分法进一步加快一下紧逼速度
2. K数之和的问题, 目前的思路也是类似将三数之和降为两数之和的办法.
假设数组有 n 个数, 求满足 K 个数之和为sum的所有组合.
a. 利用O(nlogn) 的时间排序
b. 一个循环将问题拆分为 n 个(K-1)数之和, 时间复杂度为 T(K) = O(n * T(K-1)) = O(n^(k-1))

 // 双指针夹逼
 while(left < right){
 const sum = nums[i] + nums[left] + nums[right]
 if(sum === 0){
 result.push([nums[i], nums[left++], nums[right--]])
 // push 加了之后防止还存在重复
 while(nums[left] === nums[left - 1]){
 left++
 }
 while(nums[right] === nums[right + 1]){
 right--
 } 
 }else if(sum > 0){ 
 // 这里可以使用二分法进一步加快寻找符合条件的 right, 即 nums[right]= 0 - nums[i] - nums[left]
 // right--
 }else{ // 同理也可以用二分法加快逼近速度
 // left++
 }
 }
 }

不错，对left 和 right的寻找速度用二分法确实是一个优化，很棒！K数之和的复杂度也补充得很棒。

[sisterAn]

解法： 排序 + 双指针

我们可以继续按照两数之和的思路解题，遍历数组，选定一个数（ nums[i] ）作为三数之和的第一个数，然后题目就换成了在 i+1 到 nums.length-1 中两数之和问题。

但会出现一个问题：结果中可能会出现重复的三元组

const threeSum = function(nums) {
 let map = new Map()
 let result = []
 for(let i = 0; i < nums.length - 2; i++) {
 // 第一个数
 let first = nums[i]
 for(let j = i+1; j < nums.length; j++) {
 // 第三个数
 let second = 0 - nums[j] - first
 if(map.has(second)) {
 result.push([first, second, nums[j]])
 }
 map.set(nums[j], j)
 }
 map.clear()
 }
 return result
};

// 测试
var nums = [-1, 0, 1, 2, -1, -4]
threeSum(nums)
// [[-1,0,1],[-1,2,-1],[0,1,-1]]
// 存在重复元组

你可以尝试着去除重复元组，但花费的时间、空间复杂度就高了

感谢 @thxiami 的补充，我们可以使用排序去重：

const threeSum = function (nums) {
 let set = new Set() // 使用 Set() 即可满足需求, 相对节省内存
 let result = []
 nums.sort((a, b) => (a - b))

 for(let i =0; i < nums.length - 2; i++) {
 while (nums[i] === nums[i - 1]) {i++} // 去重
 // 第一个数
 let first = nums[i]
 let j = i + 1
 while (j < nums.length) {
 // 第三个数
 let second = 0 - nums[j] - first
 let third = nums[j]

 if(set.has(second)) {
 result.push([first, second, third])

 set.add(third)
 j++

 while (nums[j] === nums[j-1]) {j++} // 去重
 } else {
 set.add(third)
 j++
 }
 }
 set = new Set()
 }
 return result
};

这里介绍另一种思路解法：排序 + 双指针

为了防止结果数组中加入重复的元素，我们可以将 nums 进行排序，例如第一个数 nums[i] === nums[i-1] 时，nums[i] 作为第一个数与 nums[i-1] 作为第一个数得到的满足条件的三元组是一致的，所以此时 nums[i] 我们将不再进行判断，避免重复三元组，当然这只是第一个数，第二个数与第三个数的判断也是类似的。

解题思路： 先数组排序，排序完后遍历数组，以 nums[i] 作为第一个数 first ，以 nums[i+1] 作为第二个数 second ，将 nums[nums.length - 1] 作为第三个数 last ，判断三数之和是否为 0 ，

• <0 ，则 second 往后移动一位（nums 是增序排列），继续判断
• >0 ，则 last 往前移动一位（nums 是增序排列），继续判断
• ===0 ，则进入结果数组中，并且 second 往后移动一位， last 往前移动一位，继续判断下一个元组

直至 second >= last 结束循环，此时， nums[i] 作为第一个数的所有满足条件的元组都已写入结果数组中了，继续遍历数组，直至 i === nums.length - 2 (后面需要有 second 、 last )

代码实现：

const threeSum = function(nums) {
 if(!nums || nums.length < 3) return []
 let result = [], second, last
 // 排序
 nums.sort((a, b) => a - b) 
 for (let i = 0; i < nums.length ; i++) {
 if(nums[i] > 0) break
 // 去重
 if(i > 0 && nums[i] === nums[i-1]) continue
 second = i + 1
 last = nums.length - 1
 while(second < last){
 const sum = nums[i] + nums[second] + nums[last]
 if(!sum){
 // sum 为 0
 result.push([nums[i], nums[second], nums[last]])
 // 去重
 while (second<last && nums[second] === nums[second+1]) second++ 
 while (second<last && nums[last] === nums[last-1]) last--
 second ++
 last --
 }
 else if (sum < 0) second ++
 else if (sum > 0) last --
 }
 } 
 return result
};

leetcode

[thxiami]

@sisterAn
使用 Map() 的第一种方法, 也是可以通过排序来去重的.

var threeSum = function (nums) {
 let set = new Set() // 使用 Set() 即可满足需求, 相对节省内存
 let result = []
 nums.sort((a, b) => (a - b))

 for(let i =0; i < nums.length - 2; i++) {
 while (nums[i] === nums[i - 1]) {i++} // 去重
 // 第一个数
 let first = nums[i]
 let j = i + 1
 while (j < nums.length) {
 // 第三个数
 let second = 0 - nums[j] - first
 let third = nums[j]

 if(set.has(second)) {
 result.push([first, second, third])

 set.add(third)
 j++

 while (nums[j] === nums[j-1]) {j++} // 去重
 } else {
 set.add(third)
 j++
 }
 }
 set = new Set()
 }
 return result
};

[Been101]

const nums = [-1, 0, 1, 2, -1, -4]

const threeSum = (nums) => {
 const res = []
 nums = nums.sort((a, b) => a - b)

 for (let i = 0; i < nums.length - 2; i++) {
 const first = nums[i]
 if (first > 0) break
 if (i && nums[i] === nums[i - 1]) {
 continue
 }
 let l = i + 1
 let r = nums.length - 1
 while (l < r) {
 const sum = first + nums[l] + nums[r]
 if (sum === 0) {
 res.push([first, nums[l], nums[r]])
 l++
 r--
 while (l < r && nums[l] === nums[l - 1]) l++
 while (l < r && nums[r] === nums[r + 1]) r--
 }

 if (sum < 0) {
 let high = r
 let mid
 while (l <= high) {
 mid = Math.floor((l + high) / 2)
 if (first + nums[mid] < -nums[r]) {
 l = mid + 1
 } else if (first + nums[mid] > -nums[r]) {
 hight = mid - 1
 } else {
 l = mid
 break
 }
 }
 l++
 }
 if (sum > 0) {
 let low = l
 let mid
 while (low <= r) {
 mid = Math.floor((low + r) / 2)
 if (first + nums[mid] < -nums[l]) {
 low = mid + 1
 } else if (first + nums[mid] > -nums[l]) {
 r = mid - 1
 } else {
 r = mid
 break
 }
 }
 r-- 
 }
 }
 }

 return res
}

[Ha0ran2001]

const nums = [-1, 0, 1, 2, -1, -4]

const threeSum = (nums) => {
 const res = []
 nums = nums.sort((a, b) => a - b)

 for (let i = 0; i < nums.length - 2; i++) {
 const first = nums[i]
 if (first > 0) break
 if (i && nums[i] === nums[i - 1]) {
 continue
 }
 let l = i + 1
 let r = nums.length - 1
 while (l < r) {
 const sum = first + nums[l] + nums[r]
 if (sum === 0) {
 res.push([first, nums[l], nums[r]])
 l++
 r--
 while (l < r && nums[l] === nums[l - 1]) l++
 while (l < r && nums[r] === nums[r + 1]) r--
 }

 if (sum < 0) {
 let high = r
 let mid
 while (l <= high) {
 mid = Math.floor((l + high) / 2)
 if (first + nums[mid] < -nums[r]) {
 l = mid + 1
 } else if (first + nums[mid] > -nums[r]) {
 hight = mid - 1
 } else {
 l = mid
 break
 }
 }
 l++
 }
 if (sum > 0) {
 let low = l
 let mid
 while (low <= r) {
 mid = Math.floor((low + r) / 2)
 if (first + nums[mid] < -nums[l]) {
 low = mid + 1
 } else if (first + nums[mid] > -nums[l]) {
 r = mid - 1
 } else {
 r = mid
 break
 }
 }
 r-- 
 }
 }
 }

 return res
}

你这个实现有问题

[XW666]

 function threeSum(nums) {
 let arr = []
 nums.sort((a, b) => (a - b))
 for (let i = 0; i < nums.length - 2; i++) {
 let v1 = nums[i]
 //去重
 if (nums[i] === nums[i - 1]) {
 continue
 }
 for (let j = i + 1; j < nums.length; j++) {
 let v2 = nums[j]
 let v3 = 0 - v1 - v2

 if (nums.slice(j + 1).includes(v3)) {
 arr.push([v1, v2, v3])
 }
 }
 }

 }

[hanmaojiang]

const nums = [-1, 0, 1, 2, -1, -4];

function threeSum(nums, res = [], sort = true) {
 if(!nums.length) return res;

 const arr = sort ? [...nums].sort() : nums;
 const sum = arr.pop();

 for(let i = 0; i< arr.length; i++) {
 const k = -sum - arr[i];

 if(arr.includes(k, i + 1)) {
 res.unshift([arr[i], k, sum]);
 break;
 }
 }

 return threeSum(arr, res, false);
}

threeSum(nums)