[Leetcode]-15 3Sum

川长思鸟来 2022-06-02 12:51 141阅读 0赞

转载地址：[https://www.cnblogs.com/grandyang/p/4481576.html][https_www.cnblogs.com_grandyang_p_4481576.html]

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)

这道题让我们求三数之和，比之前那道[Two Sum 两数之和][Two Sum]要复杂一些，我们还是要首先对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了，然后我们还要加上重复就跳过的处理，对于遍历到的数，我们用0减去这个数得到一个sum，我们只需要再之后找到两个数之和等于sum即可，这样一来问题又转化为了求two sum，这时候我们一次扫描，找到了等于sum的两数后，加上当前遍历到的数字，按顺序存入结果中即可，然后还要注意跳过重复数字。代码如下：

解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());
            for (int k = 0; k < nums.size(); ++k) {
                if (nums[k] > 0) break;
                if (k > 0 && nums[k] == nums[k - 1]) continue;
                int target = 0 - nums[k];
                int i = k + 1, j = nums.size() - 1;
                while (i < j) {
                    if (nums[i] + nums[j] == target) {
                        res.push_back({nums[k], nums[i], nums[j]});
                        while (i < j && nums[i] == nums[i + 1]) ++i;
                        while (i < j && nums[j] == nums[j - 1]) --j;
                        ++i; --j;
                    } else if (nums[i] + nums[j] < target) ++i;
                    else --j;
                }
            }
            return res;
        }
    };

![复制代码][copycode.gif]

或者我们也可以利用set的不能包含重复项的特点来防止重复项的产生，参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            set<vector<int>> res;
            sort(nums.begin(), nums.end());
            for (int k = 0; k < nums.size(); ++k) {
                if (nums[k] > 0) break;
                int target = 0 - nums[k];
                int i = k + 1, j = nums.size() - 1;
                while (i < j) {
                    if (nums[i] + nums[j] == target) {
                        res.insert({nums[k], nums[i], nums[j]});
                        while (i < j && nums[i] == nums[i + 1]) ++i;
                        while (i < j && nums[j] == nums[j - 1]) --j;
                        ++i; --j;
                    } else if (nums[i] + nums[j] < target) ++i;
                    else --j;
                }
            }
            return vector<vector<int>>(res.begin(), res.end());
        }
    };

![复制代码][copycode.gif]

参考资料：

[http://www.cnblogs.com/tenosdoit/p/3649607.html][http_www.cnblogs.com_tenosdoit_p_3649607.html]

[https://leetcode.com/discuss/23638/concise-o-n-2-java-solution][https_leetcode.com_discuss_23638_concise-o-n-2-java-solution]

[https://leetcode.com/discuss/50145/clean-straightforward-solution-using-2sum][https_leetcode.com_discuss_50145_clean-straightforward-solution-using-2sum]

[http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/][http_www.lifeincode.net_programming_leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java]

[https_www.cnblogs.com_grandyang_p_4481576.html]: https://www.cnblogs.com/grandyang/p/4481576.html
[Two Sum]: http://www.cnblogs.com/grandyang/p/4130379.html
[copycode.gif]: /images/20220602/8257b03bbccf4c2296460509fc773e16.png
[http_www.cnblogs.com_tenosdoit_p_3649607.html]: http://www.cnblogs.com/tenosdoit/p/3649607.html
[https_leetcode.com_discuss_23638_concise-o-n-2-java-solution]: https://leetcode.com/discuss/23638/concise-o-n-2-java-solution
[https_leetcode.com_discuss_50145_clean-straightforward-solution-using-2sum]: https://leetcode.com/discuss/50145/clean-straightforward-solution-using-2sum
[http_www.lifeincode.net_programming_leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java]: http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/