0015._3sum.md

15. 3sum

难度:Medium

刷题内容

原题连接

*https://leetcode.com/problems/3sum *

内容描述

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

解题方案

思路 - 时间复杂度: O(N ^ 2)- 空间复杂度: O(N)******

之前做过两个数之和等于某个数的题目，其实这题也差不多，三数之和等于0，那么我们只要让另外两个数之和等于第三个数的相反数即可，不过这里要注意会存在重复，所以要去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
   vector<vector<int> > ret;
    sort(nums.begin(),nums.end());
    for(int i = 0;i < nums.size();++i)
    {
        int t1 = i + 1,t2 = nums.size() - 1;
        if(i && nums[i] == nums[i - 1])
            continue;
        while(t1 < t2)
            if(nums[t1] + nums[t2] == -nums[i])
            {
                vector<int> v;
                v.push_back(nums[i]);
                v.push_back(nums[t1]);
                v.push_back(nums[t2]);
                ret.push_back(v);
                ++t1;
                --t2;
            }
            else if(nums[t1] + nums[t2] < -nums[i])
                ++t1;
            else
                --t2;
    }
    auto pos = unique(ret.begin(),ret.end());
    ret.erase(pos,ret.end());
    return ret;
    }
};