➕︎ 15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k，j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路
基本思想
需要整理思路，题目要求三数之和，并且数的下标不能重复，三个数的组合不能重复，所以需要去重，去重的第一步就是排序，这样相同的元素聚集在一起，以一个元素出发搜索其他所有符合要求的元素形成了三元组，下一次搜索时就不能从这个元素出发了，所以需要第一次去重，体现在代码中为：
1
2
3
| //防止从重复的a出发
if(i>0&&nums[i]==nums[i-1])
continue;
|
为了统计出所有符合要求的三元组，从一个元素出发，剩下的两个元素可以从余下元素的两端开始统计，也就是i+1和nums.size()-1的位置，这样就可以防止三个元素的下标重复为什么左边从i+1是因为之前的元素都已经被统计了，也就是第一个元素是从头开始的，如果左边从头开始，会出现很多重复的三元组
关于左边从i+1开始需要好好理解
当三个元素形成一个合法的三元组时，需要注意左右两端的元素也不能重复，此时需要第二次去重，体现在代码中为：
1
2
3
4
5
| //将左右两个数去重，防止出现重复的三元组
while(left<right&&nums[right]==nums[right-1])
right--;
while(left<right&&nums[left]==nums[left+1])
left++;
|
整体的思路就是从一个数出发，统计出剩下的两个数，统计的过程中需要经历两次去重
执行流程
对给定的元素排序
依次从数组中的每一个元素出发，从余下的元素中试图统计出剩下的两个元素组成合法的三元组
判断当前出发的元素是否已经被统计过，第一次去重
从余下的元素中找出符合要求的两个元素
- 三数之和大于0，右边的数需要变小
- 三数之和小于0，左边的数需要变大
- 三数之和等于0，形成合法的三元组
- 对左右两边的元素去重，第二次去重
- 形成三元组，将三元组加入结果容器中
- 继续尝试统计出新的三元组
从新的元素出发，继续统计
返回结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//为了去重，先对容器中的元素进行排序
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<nums.size();++i){
int a=i;
//数组经过排序，当前元素都大于0，后面的元素相加肯定不可能等于0
if(nums[a]>0)
return res;
//防止从重复的a出发
if(i>0&&nums[i]==nums[i-1])
continue;
//到这里就是三个数中的第一个数不是重复的
int left=i+1;
int right=nums.size()-1;
//因为三个数的下标不能相等，所以这里left!=right
while(left<right){
int sum=nums[a]+nums[left]+nums[right];
//当前三个数的和大于0，说明需要缩小，移动右边的下标
if(sum>0){
right--;
}
//当前三个数的和小于0，说明需要放大，移动左边的下标
else if(sum<0){
left++;
}
//当前三个数的和等于0
else{
//将左右两个数去重，防止出现重复的三元组
while(left<right&&nums[right]==nums[right-1])
right--;
while(left<right&&nums[left]==nums[left+1])
left++;
//到这里说明有一个三元组出现
vector<int> temp;
temp.push_back(nums[a]);
temp.push_back(nums[left]);
temp.push_back(nums[right]);
res.push_back(temp);
//继续从当前的a出发统计新的不重复的三元组
right--;
left++;
}
}
}
return res;
}
};
|
总结
主要是需要将问题分解，三数之和分解成一个图：
每次从一个数出发，从余下的元素中试图找出另外两个合法的元素，理解了这幅图就相当于理解了题目的解法
