题目链接:
三数之和
题意：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
1
2
3
4
| [
[-1, 0, 1],
[-1, -1, 2]
]
|
思路:
双指针+剪枝，具体操作看代码
参考代码：
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
| class Solution
{
map<int,int>mp;
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
sort(nums.begin(), nums.end());
vector<vector<int>> vec;
int n = nums.size();
string s;
for (int i = 0; i < n; i++)
{
int l = i + 1, j = i + 2;
if(mp[nums[i]])
continue;
mp[nums[i]]=1;
while (j < n)
{
while ((nums[i] + nums[l] + nums[j]) < 0 && l < j && j < n)
l++;
while ((nums[i] + nums[l] + nums[j]) > 0 && l > i + 1 && l < j)
l--;
if ((nums[i] + nums[l] + nums[j]) == 0 && l < j && j < n)
{
vec.push_back(vector<int>{nums[i], nums[l], nums[j]});
}
j++;
}
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
return vec;
}
};
|
