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;
}
};
