(难度Medium) Problem 15: 3Sum

Problem 15: 3Sum

### 链接

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

Medium

### 题干

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.

### 样例

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

### 题解

#### 解法一： 利用2Sum

LeetCode的第一题就是2Sum问题，给定一个数组和一个target数字。要求从数组当中找到两个数的pair对，使得两个数的和等于target。

class Solution {
public:
vector<vector<int>> getIndex(vector<int>& nums, int target, int index) {
map<int, int> mp;
int n = nums.size();
vector<vector<int>> ret;
set<int> st;
// 传入下标index，表示从index之后的位置开始进行2Sum
for (int i = index+1; i < n; i++) {
if (mp.count(target-nums[i])) {
if (st.count(target-nums[i]) || st.count(nums[i])) continue;
vector<int> vt;
vt.push_back(target-nums[i]);
vt.push_back(nums[i]);
ret.push_back(vt);
st.insert(nums[i]);
st.insert(target-nums[i]);
}
mp[nums[i]] = i;
}
return ret;
}

vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ret;
set<pair<int, int>> st;
set<int> s;
for (int i = 0; i < n; i++) {
if (s.count(nums[i])) continue;
vector<vector<int>> tmp = getIndex(nums, -nums[i], i);
if (tmp.size() > 0) {
s.insert(nums[i]);
int m = tmp.size();
for (int j = 0; j < m; j++) {
vector<int> cur;
vector<int> nm = tmp[j];
cur.push_back(nums[i]);
cur.push_back(nm[0]);
cur.push_back(nm[1]);
sort(cur.begin(), cur.end());
// 判断答案是否出现过
if (st.count(pair<int, int>(cur[0], cur[1]))) continue;
st.insert(pair<int, int>(cur[0], cur[1]));
ret.push_back(cur);
}
}
}
return ret;
}
};

#### 解法二 正负数分组

`
class Solution {
public:

//2 Sum
vector> getIndex(vector& nums, int target) {
map mp;
int n = nums.size();
vector> ret;
set st;
for (int i = 0; i < n; i++) { if (mp.count(target-nums[i])) { if (st.count(target-nums[i]) || st.count(nums[i])) continue; vector vt;
vt.push_back(target-nums[i]);
vt.push_back(nums[i]);
ret.push_back(vt);
st.insert(nums[i]);
st.insert(target-nums[i]);
}
mp[nums[i]] = i;
}
return ret;
}

vector> threeSum(vector& nums) {
vector neg;
vector zero;
vector posi;
set negset;
set posiset;
vector vt;
vector> ret;
int n = nums.size();
// 所有数分为0、正数和负数
for (int i = 0; i < n; i++) if (nums[i] < 0) {
neg.push_back(nums[i]);
negset.insert(nums[i]);
}
else if (nums[i] == 0) zero.push_back(0);
else {
posi.push_back(nums[i]);
posiset.insert(nums[i]);
}