15. 3Sum
15. 3Sum
题目
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j
, i != k
, and j != k
, and nums[i] + nums[j] + nums[k] == 0
.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
题目大意
给定一个数组,要求在这个数组中找出 3 个数之和为 0 的所有组合。
解题思路
这一题比较麻烦的一点在于,最后输出解的时候,要求输出不重复的解。
数组中同一个数字可能出现多次,同一个数字也可能使用多次,但是最后输出解的时候,不能重复。例如 [-1, -1, 2] 和 [2, -1, -1]、[-1, 2, -1] 这 3 个解是重复的。
这就需要排序和去重,使用对撞指针寻找三数之和为 0 的组合。
先对数组进行排序,i 从后往前扫描,这里同样需要注意数组中存在多个重复数字的问题。i 在循环的时候和后一个数进行比较,如果相等,i 继续往前移,直到移到下一个和前一个数字不同的位置。
j,k 两个指针开始一前一后对撞。j 从数组首位开始,k 为 i 的前一个数字,由于经过排序,所以 j < k。对比三个数的和与 target 的大小,小于 target,j 往后移动;大于 target,k 往前移动,寻找三数之和为 target 的组合,移动指针时注意去重。
代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
nums = nums.sort((a, b) => a - b);
const target = 0;
let res = [];
for (let i = nums.length - 1; i > 1; i--) {
// 排除 i 重复的情况
if (i === nums.length - 1 || nums[i] != nums[i + 1]) {
let j = 0;
let k = i - 1;
let sum = target - nums[i];
while (j < k) {
if (nums[j] + nums[k] === sum) {
res.push([nums[i], nums[j], nums[k]]);
// 排除 j 重复的情况
while (j < k && nums[j] === nums[j + 1]) {
j++;
}
// 排除 k 重复的情况
while (j < k && nums[k] === nums[k - 1]) {
k--;
}
j++;
k--;
} else if (nums[j] + nums[k] < sum) {
j++;
} else {
k--;
}
}
}
}
return res;
};
相关题目
- [1. 两数之和](./0001.md)
- [16. 最接近的三数之和](./0016.md)
- [18. 四数之和](./0018.md)
- [🔒 3Sum Smaller](https://leetcode.com/problems/3sum-smaller)
- [2367. 算术三元组的数目](https://leetcode.com/problems/number-of-arithmetic-triplets)
- [2908. Minimum Sum of Mountain Triplets I](https://leetcode.com/problems/minimum-sum-of-mountain-triplets-i)
- [2909. Minimum Sum of Mountain Triplets II](https://leetcode.com/problems/minimum-sum-of-mountain-triplets-ii)