给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
思路:
1.三重循环遍历,毫无疑问地超时了
2.先排序,两重循环加上二分查找,也超时了
3.先排序,遍历nums数组小于等于0的数作为第一个数sum,设置头尾指针,看头尾指针所指元素相加是否为-sum,如果相等,若不重复则记录,尾指针--头指针++,如果大于-sum,尾指针--,如果小于-sum,头指针++。
关键就是看有没有重复的部分了,就是要看结果的第一个元素和第二个元素是否相等,对于结果的第一个元素,排序后的数组只要关心当前元素的sum值是否等于上一项元素的sum值就好了,同理,对于第二个元素,排序后的数组只要关心当前值是否与上一项值相等即可,实现代码如下。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
if(nums.size()<3)
{
return res;
}
sort(nums.begin(),nums.end());
int sum=INT_MIN;
for(int i=0;i<nums.size()-2;i++)
{
if(nums[i]<=0)
{
temp.push_back(nums[i]);
if(sum==0-nums[i])
{
temp.pop_back();
continue;
}
sum=0-nums[i];
int front=i+1;
int back=nums.size()-1;
int second=nums[front]-1;
while(front<back)
{
if(nums[front]+nums[back]==sum)
{
if(second!=nums[front])
{
second=nums[front];
temp.push_back(second);
temp.push_back(nums[back]);
res.push_back(temp);
temp.pop_back();
temp.pop_back();
}
front++;
back--;
}
else if(nums[front]+nums[back]>sum)
{
back--;
}
else
{
front++;
}
}
temp.pop_back();
}
}
return res;
}
};
网友评论