LeetCode第15题:3Sum(C++)详解
3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
题目解析:求取出数组中三个数字相加等于0的所有组合情况,并将其作为集合返回。
解题思路:
1.先将给定的数组进行排序,可得:
【-4,-1,-1,0,1,2】
2.如果将-4作为三个数字的第一个,那么需要从数组中第二位开始,寻找二个数字,其三个数字相加为0;
3.设置二个指针分别指向数组第二个及最后一个,分别为-1 及 2,此时-4+(-1)+ 2 不等于0;则表示-4不可能是三
个数的第一个数字;
4.此时我们需要自增1,将数组第二位-1作为三个数的第一个数, 第一个指针指向数组第三个数-1,第二个指针指向
最后一位2,相加为0,即为一种答案;
5.二个指针继续向中间循环,即可得到-1,0,1,符合条件,继续循环直至没有符合条件的三个数,此时以-1为开头数字的所有结果都已经加入返回结果中;
6.继续第三个数字-1,因为-1为第一个数字的组合都已经加入,此时-1可填出本次循环;
7.以上述步骤进行遍历即可。
解题代码:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
std::sort(nums.begin(),nums.end());//对给定数组进行排序
vector<vector<int>> result;
for(int i=0;i<nums.size();i++)
{
if(i>0 && i<nums.size() && (nums[i] == nums[i-1]))//每次循环会将开头数字的所有组合寻找出来,当下一位数字等于前一位时,跳出当前循环
{
continue;
}
int left = i + 1;//左侧指针
int right = nums.size() - 1;//右侧指针
while(left < right)//nums[i]为第一个数字,然后由二个指针进行遍历,找出另外二个数字的所有组合
{
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0)//三数相加大于0,右指针向左移
{
right --;
}
else if(sum < 0)//三数相加小于0,左指针右移
{
left ++;
}
else//等于0的情况
{
result.push_back(vector<int>{nums[i],nums[left],nums[right]});//将组合加入结果中
while(left < right && nums[left] == nums[left + 1])//左指针继续右移,不允许相同的集合,left++
{
left ++;
}
while(left < right && nums[right] == nums[right - 1])//同理
{
right --;
}
left ++;//向右移位
right --;//向左移位 上述解析得到【-1,0,1】的组合对应
}
}
}
return result;
}
};
算法性能:
总结:算法性能一般,主要核心是二次遍历,找出三个数字的所有情况,基本属于暴力**吧,大家有更好的方法,欢迎批评指正,也欢迎大家点赞,谢谢。
work work!