本文主要是介绍LeetCode 2.1.8 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)
问题分析：我们对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了。这里我们可以先做个剪枝优化，就是当遍历到正数的时候就break，为啥呢，因为我们的数组现在是有序的了，如果第一个要fix的数就是正数了，那么后面的数字就都是正数，就永远不会出现和为0的情况了。然后我们还要加上重复就跳过的处理，处理方法是从第二个数开始，如果和前面的数字相等，就跳过，因为我们不想把相同的数字fix两次。对于遍历到的数，用0减去这个fix的数得到一个target，然后只需要再之后找到两个数之和等于target即可。我们用两个指针分别指向fix数字之后开始的数组首尾两个数，如果两个数和正好为target，则将这两个数和fix的数一起存入结果中。然后就是跳过重复数字的步骤了，两个指针都需要检测重复数字。如果两数之和小于target，则我们将左边那个指针i右移一位，使得指向的数字增大一些。同理，如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小一些
代码：
class Solution
{
public:vector<vector<int>>threeSum(vector<int>& num){vector<vector<int>> result;sort(num.begin(),num.end());//排序数组if(num.empty() || num.back() < 0 || num.front() > 0){return result;}for(int k = 0;k < num.size();k++){if(num[k] > 0){break;}if(k > 0 && num[k] == num[k - 1])//防止重复{continue;}int target = 0 - num[k];int p1 = k + 1;//importantint p2 = num.size() - 1;while(p1 < p2){if(num[p1] + num[p2] == target){result.push_back(num[k],num[p1],num[p2]);while(p1 < p2 && num[p1] == num[p1]){p1++;}while(p1 < p2 && num[p2] == num[p2]){p2--;}++p1;--p2;}else if(num[p1] + num[p2] < target){p1++;}else{p2--;} }}return result;}
};
这篇关于LeetCode 2.1.8 3Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
