【LeetCode】15. 3Sum – TK-Xiong`s Blog

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.

题目大意：找到三个数的和为0.

Note: 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]
]

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

原题链接：https://leetcode.com/problems/3sum/description/

就是找三个数的和为0的数组，不能有重复数组。

这道题是之前在58同城面试的时候碰到的。

当时的思路是排序，然后处理。

现在看来还是Too Young Too Simple…

这里首先是用到了Two Sum这道题的思想，将三个数的和为0 变化为两个数的和为target。

然后还涉及一些去重优化。代码速度比较坑，最快到 102ms，慢的话到122ms…差不多了.

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

class Solution {

public:

vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> ans;

sort(nums.begin(), nums.end());

for(int i = 0; i < nums.size(); i++)

{

if(nums[i] > 0) break;

if(i > 0 && nums[i] == nums[i-1]) continue;

int target = 0 - nums[i];

int beg = i + 1;

int end = nums.size() - 1;

while(beg < end)

{

if(nums[beg] + nums[end] == target)

{

ans.push_back({nums[i], nums[beg], nums[end]});

while (beg < end && nums[beg] == nums[beg+1]) ++beg;

while (beg < end && nums[end] == nums[end-1]) --end;

--end;

++beg;

}

else if(nums[beg] + nums[end] < target)

{

++beg;

}

else

{

--end;

}

return ans;

}

};

以上是代码。

接下来是参考链接：

http://blog.csdn.net/nanjunxiao/article/details/12524405

其他:

参考链接提到的Hash也想过，不过在3Sum下不太实用，就放弃了。

关于Set去重这个，我不太建议，个人尝试过，不太快，大概600ms左右…勉强通过的速度吧.

【LeetCode】15. 3Sum

Tagged on: C++ LeetCode