首页 > 代码库 > 三数之和
三数之和
题目描述：
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
注意事项
在三元组(a, b, c)，要求a <= b <= c。
结果不能包含重复的三元组。
样例
如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：
(-1, 0, 1)
(-1, -1, 2)
解法1：三层for循环，时间复杂度O(n^3)
//解法1: O(n^3)
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
vector<vector<int> > ans;
int n = nums.size();
map<vector<int>, int> mp;
vector<int> temp;
for (int i=0; i<n; ++i) {
for (int j=i+1; j<n; ++j) {
for (int k=j+1; k<n; ++k) {
if (nums[i]+nums[j]+nums[k] == 0) {
temp.resize(0);
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
temp.resize(3);
sort(temp.begin(), temp.end());
if (mp[temp]) {
continue;
}else {
mp[temp]++;
ans.push_back(temp);
}
}
}
}
}
return ans;
}
};
解法2：将原数组备份，遍历每一个数val，两层for循环查找是否能找到两数之和为-val。注意：三个数相等时、或任意两数相等时的情况和去重。
时间复杂度O(n^2).
//解法2：O(n^2)
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
vector<int> ori_num;
map<int, int> cnt;
for (int i=0; i<nums.size(); ++i) {
ori_num.push_back(nums[i]);
cnt[nums[i]]++;
}
vector<vector<int> > ans;
sort(nums.begin(), nums.end());
vector<int> temp;
map<vector<int>, int> vector_mp;
for (int i=0; i<nums.size(); ++i) {
for (int j=i+1; j<nums.size(); ++j) {
int tot = nums[i] + nums[j];
auto iter = find(ori_num.begin(), ori_num.end(), 0-tot);
if (nums[i] == 0-tot) {
if (cnt[nums[i]] < 2) continue;
}
if (nums[j] == 0-tot) {
if (cnt[nums[j]] < 2) continue;
}
if (nums[i] == nums[j] && nums[i] == 0-tot) {
if (cnt[nums[i]] < 3) continue;
}
if (iter != ori_num.end()) {
temp.resize(0);
temp = {0-tot, nums[i], nums[j]};
temp.resize(3);
sort(temp.begin(), temp.end());
if (vector_mp[temp] == 0)
ans.push_back(temp);
vector_mp[temp]++;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
解法3：对原数组从小到大排序，从左到右遍历val，然后二分查找两个数之和是-val的。左边界i+1,右边界n-1，如果当前和=-val，加入答案，否则如果小于，左边界右移，相反右边界左移。可以利用map去重，也可以利用set容器不能包含重复项的特点来去重。时间复杂度O(nlog(n)).
/// 解法3：对原数组从小到大排序，从左到右遍历，然后找两个数之和是-target的。
class Solution {
public:
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
sort(nums.begin(), nums.end());
set<vector<int> > st;
for (int i=0; i<nums.size(); ++i) {
int val = nums[i];
if (val > 0) break;
int l = i + 1;
int r = nums.size() - 1;
while(l < r) {
int temp = nums[l] + nums[r];
if (temp == -val) {
st.insert({val, nums[l], nums[r]});
while(l<nums.size()-1 && nums[l+1] == nums[l]) l++;
while(nums[r-1] == nums[r] && r > 0) r--;
}else if (temp > -val) r -= 1;
else if (temp < -val) l += 1;
}
}
vector<vector<int> > ans;
set<vector<int> >::iterator iter;
for (iter=st.begin(); iter != st.end(); ++iter) {
ans.push_back(*iter);
}
return ans;
}
};
三数之和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。