15.3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: (Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c))The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
从数组中计算出和与给定值相等的元素组成的新数组，以数组形式返回。Leetcode上的题目似乎有变化，原先还有一个条件是返回的数组中元素必须以升序排列。
最笨的方法就是三重循环，O(n^3)的时间复杂度，想想都可怕。
再来分析题目要求:
- 以数组形式返回
- 返回结果不能重复
- 返回结果以升序排列
以上我们用一大堆if语句都可以完成，不过如果数组在最初是有序的，问题就简化了许多。声明left,mid,right作为待返回数组的三个数的下标，其中left最小，right最大。
那么三个数之和等于0，只要确定一个数，不就转化为2Sum问题了吗？所以我们需要一层外循环
for(left=0;left<size&&nums[left]<=0;left++)
之后mid和right两个指针从两边向中间扫描，发现符合条件的进行记录
while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}
这样，似乎我们的算法可以解决这个问题了，然而还需要处理重复的问题。于是修改代码如下:
for(left=0;left<size&&nums[left]<=0;left++){
tmp=0-nums[left];
mid=left+1;
right=size-1;
while(mid<right){
if(nums[mid]+nums[right]==tmp){
int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
vector<int>triplet(3,0);
triplet[0]=nums[left];
triplet[1]=nums[mid];
triplet[2]=nums[right];
res.push_back(triplet);
while(mid<right&&nums[++mid]==tmp_mid);/*防止mid造成重复*/
while(mid<right&&nums[--right]==tmp_right);/*防止right造成重复*/
}
else if(nums[mid]+nums[right]<tmp)
mid++;
else
right--;
}
while(left+1<size&&nums[left]==nums[left+1])/*防止*/
left++;
}
问题就得到了解决。