leetcode15：三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]输入：nums = []
输出：[]输入：nums = [0]
输出：[]提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105💡 思路：三数之后，转化为2数之和
先看两两相加的规则
// var arr = [1,2,3]
// 1+2
// 1+3
// 2+3
for (var i = 0; i < arr.length; i++) {
for (var j = i + 1; j < arr.length; j++) {
// 两数之和核心逻辑
}
}两数之和等于第三数的代码
var arr = [1, 2, 4, 5, 6, 9];
var res = [];
for (var i = 0; i < arr.length; i++) {
for (var j = i + 1; j < arr.length; j++) {
var ret = arr[i] + arr[j];
var idx = arr.indexOf(ret);
if (idx !== -1) {
res.push([arr[i], arr[j], ret]);
}
}
}自己的实现代码
- 注意去重
- 双层循环
- 原理：
a+b+c =0; 转化为： a+b=-c;
var arr = [-1, 0, 1, 2, -1, -4];
var res = [];
var uniq = {};
for (var i = 0; i < arr.length; i++) {
for (var j = i + 1; j < arr.length; j++) {
// 两数之和核心逻辑
var ret = arr[i] + arr[j];
var idx = arr.indexOf(-ret);
var uniqKey = [arr[i], arr[j], -ret].sort().join(',');
// 目标不是同一个 idx
var hasSameIdx = [ i, j ].includes(idx);
if (idx !== -1 && !uniq[uniqKey] && !hasSameIdx) {
uniq[uniqKey] = true;
res.push([arr[i], arr[j], -ret]);
}
}
}
console.log(res);
// [ [ -1, 0, 1 ], [ -1, -1, 2 ] ]