首页 > > 程序设计 > C/C++ >

#leetcode刷题之路15-三数之和

2019-03-06 07:15:12来源：博客园阅读 ()

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路：先对vector进行排序，这样的话如果前两个数之和大于9，那么也就可以直接pass了

然后把vector中的数依次放入map中，暴力循环，每次计算前两个数之和，再在map中找到第三个数，存在一个set中，再把set存在一个set中，避免重复。

在不重复的情况下把这三个数放入vector中。

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include <algorithm>
using namespace std;


vector<vector<int>> threeSum(vector<int>& nums) {
    map<int,int> temp;
    vector<vector<int>> ans;
    set<set<int>> anss;
    int len = nums.size();
    int n = 0;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < len; i++)
    {
        temp[nums[i]] = i;
    }
    for (int i = 0; i < len; i++){
        for (int j = i+1; j < len; j++)
        {
            int num = -nums[i] - nums[j];
            if (num>0) continue;
            map<int, int> ::iterator add = temp.find(num);
            if (add == temp.end() || add->second <= j) continue;
            set<int> t;
            t.insert(nums[i]);
            t.insert(nums[j]);
            t.insert(add->first);
            //cout << nums[i] << nums[j] << add->first << endl;
            if (anss.count(t) == 0)
            {
                anss.insert(t);
                vector<int> t;
                t.push_back(nums[i]);
                t.push_back(nums[j]);
                t.push_back(add->first);
                ans.push_back(t);
                cout << nums[i] << nums[j] << add->first << endl;
            }

        }
    }
    return ans;
}


int main(){
    vector<int> a = { -1, 0, 1, 2, -1, -4 };
    vector<vector<int>> ans = threeSum(a);
    system("pause");
    return 0;
}