题目描述
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，每个数只能选择一次。这道题的难点在于去重，因为可能有重复的数出现，使用容器来去重并不方便，最方便是手工去重。手工去重需要先进行排序，这里去重需要进行两次。这道题的大致思路是先固定一个值，然后通过双指针扫描求出另外两个值。这也是需要先进行排序的原因，双指针前后同时进行扫描。固定一个值后的组合也可能不止一种，所以扫描结束的条件是两个指针重合，故在这个过程中也需要进行去重。去重就是跳过相同的数即可，因为已经排序过，所以只需要一边的指针进行去重即可。在遍历完固定的一个数组合后，还需要进行第二次去重，即下一个遍历的数不能和上一个数相同。
AC代码如下：
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {
int length = nums.size();vector<vector<int>> result;sort(nums.begin(), nums.end());for(int i = 0; i < length; ++i){
vector<int> temp;int left = i + 1, right = length - 1;//初始化双指针if(nums[i] > 0)//第一个固定的数不可能是正数，因为后面的数都比它大{
break;}int target = -nums[i];temp.push_back(nums[i]);while(left < right)//扫描结束条件{
if(nums[left] + nums[right] == target)//符合条件{
temp.push_back(nums[left]);temp.push_back(nums[right]);result.push_back(temp);temp.pop_back();temp.pop_back();++left;--right;while((right > 0) && (nums[right] == nums[right+1]))//扫描中去重{
--right;}}else if(nums[left] + nums[right] < target){
++left;}else{
--right;}}while((i+1 < length) && (nums[i] == nums[i+1]))//扫描结束后再次去重{
++i;}}return result;}
};