左嘉

用户名：zuojia

访问量：88641

签　名：

等　　级
排　　名	5
经　　验	34540
参赛次数	226
文章发表	72
年　　龄	40
在职情况	在职
学　　校	北京理工大学
专　　业

　　自我简介：

TA的其他文章

数日子（C语言代码）
浏览：1130

最多的水（C++代码）
浏览：854

蓝桥杯算法提高VIP-删除重复元素-题解(C语言代码)
浏览：622

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

3sum-题解(C++代码)

　　作者: 左嘉　　　　发表时间：2019-06-09 23:18:09 浏览：301　|　评论：0　

原题链接：3sum

#### 解题思路:
我们来分析一下这道题的特点，要我们找出三个数且和为0，那么除了三个数全是0的情况之外，肯定会有负数和正数，我们还是要先fix一个数，然后去找另外两个数，我们只要找到两个数且和为第一个fix数的相反数就行了，如果能更有效的定位呢？我们肯定不希望遍历所有两个数的组合吧，所以如果数组是有序的，那么我们就可以用双指针以线性时间复杂度来遍历所有满足题意的两个数组合。
我们对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了。这里我们可以先做个剪枝优化，就是当遍历到正数的时候就break，为啥呢，因为我们的数组现在是有序的了，如果第一个要fix的数就是正数了，那么后面的数字就都是正数，就永远不会出现和为0的情况了。然后我们还要加上重复就跳过的处理，处理方法是从第二个数开始，如果和前面的数字相等，就跳过，因为我们不想把相同的数字fix两次。对于遍历到的数，用0减去这个fix的数得到一个target，然后只需要再之后找到两个数之和等于target即可。我们用两个指针分别指向fix数字之后开始的数组首尾两个数，如果两个数和正好为target，则将这两个数和fix的数一起存入结果中。然后就是跳过重复数字的步骤了，两个指针都需要检测重复数字。如果两数之和小于target，则我们将左边那个指针i右移一位，使得指向的数字增大一些。同理，如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小一些，代码如下：
**解法一：**
```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
        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;
    }
};
```
或者我们也可以利用set的不能包含重复项的特点来防止重复项的产生，那么我们就不需要检测数字是否被fix过两次，不过个人觉得还是前面那种解法更好一些，参见代码如下：
**解法二：**
```cpp
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
        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());
    }
};
```
--------------------- 
作者：[Grandyang](https://www.cnblogs.com/grandyang/ "仰天长啸仗剑红尘，冬去春来寒暑几更...")
来源：博客园 
原文：https://www.cnblogs.com/grandyang/p/4481576.html
#### 注意事项：
这里给出另一个测试用例：-1 0 1 1 1 1 -4 4 2 2 -2 -1 -4 6 7 -3 3 3 3 -3；编写main函数观察测试结果，代码如下：
```cpp
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 参见“解题思路”
    }
};
int main(){
    int a;
    vector<int> nums;
    Solution s;
    while(cin>>a) nums.push_back(a);
    vector<vector<int>> res=s.threeSum(nums);
    for(int i=0;i<res.size();i++) // 访问矢量中的矢量
        cout<<res[i][0]<<" "<<res[i][1]<<" "<<res[i][2]<<endl;
    return 0;
}
```
测试结果如下：
-4 -3 7
-4 -2 6
-4 0 4
-4 1 3
-4 2 2
-3 -3 6
-3 -1 4
-3 0 3
-3 1 2
-2 -1 3
-2 0 2
-2 1 1
-1 -1 2
-1 0 1
#### 参考代码：
```cpp
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 参见“解题思路”
};
int main(){
    int a;
    vector<int> nums;
    Solution s;
    while(cin>>a) nums.push_back(a);
    cout<<(s.threeSum(nums)).size();
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

左嘉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

3sum-题解(C++代码)

评论区

精彩推荐

C语言考试练习题_一元二次方程（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-立方和不等式（C语言代码）

计算质因子（C++代码）

1012题解

有关字符，字符串的输入输出函数说明

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

左嘉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （Java代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

3sum-题解(C++代码)

评论区

精彩推荐

C语言考试练习题_一元二次方程 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-立方和不等式 （C语言代码）

计算质因子 （C++代码）

1012题解

有关字符，字符串的输入输出函数说明

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

母牛的故事（C语言代码）

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-立方和不等式（C语言代码）

计算质因子（C++代码）