15. 三数之和
LeetCode题目要求
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例1
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
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 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
解题思路
使用双指针移动的方式来计算三个元素的和 0。
大致思路为:遍历数组,通过 i 指针,left指针不断向后移,right指针不断向前移动的方式,通过三个指针对应的值相加,如果等于0 就找到了结果。
需要注意的是:由于要求结果不能重复,那么在处理 i 索引的值时,如果已经处理过,那么就可以跳过,left 及 right 处理是一样的道理,为找到结果是 left 及 right 正常移动,如果出现和为 0 时,那么需要处理 left 向后移动的下一个值是否与当前值相等,或者 right 向前移动的下一个值是否与当前值相等,因为相等的就是重复的。
如图1,和为0 小于 < 0 , 所以 left 一直要向右移动:
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230104222900780-1270067550.png)
如图2,下一次循环,i向后移动,出现结果,如果有重复需去重
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230104223010713-525979712.png)
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230104223051082-1144622932.png)
看代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
// 先排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 由于是从小到大排序后的数,如果第一个数大于0,再加后面的数肯定不会等于0
if (nums[i] > 0) {
break;
}
// 去重 如果当前值与前一个一样,就不需要再处理了
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
// 双指针法, 开始指针、左指针、右指针、
int left = i + 1;
int right = nums.length - 1;
// 当 left < right 时就一直移动,left 和 right,并 3 数相加,判断是否为 0
while (left < right) {
int c = nums[i] + nums[left] + nums[right];
if (c < 0) {
left++;
} else if (c > 0) {
right--;
} else {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
}
}
return res;
}
}
重难点
元素不能重复,怎么做去重处理
附:学习资料链接