## 题目
给你一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 $a + b + c = 0$ ?请你找出所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
解题
方法一:排序 + 双指针
思路
将数组排好序,遍历一个数 nums[i]
使三数之和 ($a + b + c = 0$) 转换为两数之和 ($b + c = -a$)
然后定下左指针 left
初始指向 i+1
表示第二个数,右指针 right
初始指向 nums.length-1
表示第三个数,两个指针向中间移动直至相撞时停止
计算三数之和 sum
,由于数组是升序的,则有:
- 当 $sum<0$ 时需要将
sum
增大,故将左指针右移 - 当 $sum>0$ 时需要将
sum
减小,故右指针左移 - 当 $sum=0$ 时 ${nums[i], nums[left], nums[right]}$ 是一组合法的解 这时将三个数字加入结果集中,左右指针继续向中间移动,这时移动的过程中若遇到连续的相同数字,为防止有效解重复,要跳过这些相同的数字
代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
// 遍历以确定下来一个数
for (int i = 0; i < len; i++) {
// 遇到连续的相同数字则跳过
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 初始化左右指针
int left = i + 1, right = len - 1;
// 终止条件: 两指针相撞
while(left < right) {
// 计算三数之和
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
// 小了 需要增大 左指针右移
left++;
} else if (sum > 0) {
// 大了 需要减小 右指针左移
right--;
} else {
// 相同 得出一组合法的解
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 继续向中移动
left++;
right--;
// 遇到连续的相同数字跳过
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
while(left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return ans;
}
}
剪枝优化
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
if (len < 3 || nums[0] > 0 || nums[len - 1] < 0) {
// 剪枝: 数组长度不够或者数组里元素都大于或都小于0不存在解
return ans;
}
// 剪枝: 第一个数字如果大于0 其与右边两个数字加和的结果不可能是0了
for (int i = 0; i < len && nums[i] <= 0; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = len - 1;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
while(left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return ans;
}
}
评论区