我正在做3Sum问题:https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/776/
简单的问题:给定一个整数数组nums，返回所有的三组[nums[i], nums[j], nums[k]]，使得i != j,i != k,j != k和nums[i] + nums[j] + nums[k] == 0。注意，解决方案集不能包含重复的三元组。
我的问题:我有一个解决方案，它确实返回一些但不是所有可能的三胞胎，我不明白我在哪里出错。其次，我的算法是O(N^2 log N)，欢迎任何改进的建议。
Input:
[-1,0,1,2,-1,-4,-2,-3,3,0,4]
Output:
[[-3,-1,4],[-3,0,3],[-4,1,3],[-2,0,2],[-4,0,4]]
Expected:
[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
算法:我已经将我的算法连同注释一起包含在代码中，但这里是要点-对于每一对数字，我将它们的sum存储为key，并将给我sum的数字索引存储为value。然后在循环中遍历每个元素并检查target值与该数字之间的差异是否作为map中的key出现。如果是，并且所有索引都不相等，则将其添加到最终返回的vector中。
代码:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums) {
/*
* If less than 3 elements are passed return empty vector
*/
if (nums.size() < 3)
return {};
int target = 0; // all three numbers sum up to 0 as given
vector<vector<int>> outer; // this is returned by the function
unordered_map<int, vector<int>> umap; // unordered_map for keeping sum and indices
/*
* Calculate sum of each pair of numbers
* Store the sum as key and the pair as value
* i != j is guaranteed
*/
for (int i = 0; i < nums.size(); i++)
for (int j = i + 1; j < nums.size(); j++)
umap[nums[i] + nums[j]] = {i, j};
/*
* Go through each element and calculate the difference
* between target and that element, this gives the sum
* of the other two elements.
* Look for the sum in unordered_map
* If it is present check if all three indices are not equal to each other
*/
for (int i = 0; i < nums.size(); i++) {
vector<int> inner;
int diff = target - nums[i];
auto it = umap.find(diff);
inner = umap[diff];
if (it != umap.end() && i != inner[0] && i != inner[1]) {
inner.push_back(i);
vector<int> tmp;
for (auto &j: inner)
tmp.push_back(nums[j]); // push actual numbers instead of indices
sort(tmp.begin(), tmp.end()); // sort the inner three elements
if (find(outer.begin(), outer.end(), tmp) == outer.end()) // for removing duplicates
outer.push_back(tmp);
}
}
return outer;
}
int main() {
vector<int> v{-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
vector<vector<int>> ret = threeSum(v);
for (auto &i: ret) {
for (auto j: i)
cout << j << " ";
cout << endl;
}
}
您的错误用输入[-5, 1, 2, 3, 4]来演示。
问题是5 == 1+4 == 2+3。您的map将只存储这些对中的一个作为该键的值，因此它不会记录两个对都可以导致该键的事实。
关键思想与TwoSum问题相同。当我们固定第一个数时，可以按照与TwoSum相同的推理找到第二个和第三个数。
唯一的区别是LEETCODE的TwoSum问题有一个唯一的解。然而，在ThreeSum中，我们可以找到多个重复的解决方案。大多数OLE错误都发生在这里，因为您可能最终得到一个具有如此多副本的解决方案。
naïve对于重复的解决方案将使用如下的STL方法:
std::sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
但是，根据我的意见，这种方式会使你的时间消耗几乎增加一倍。
一个更好的方法是跳过已经扫描的数字，不管它是否是某个解决方案的一部分。
如果这三个数构成一个解，我们可以安全地忽略它们的所有重复项。
我们可以对所有三个数字都这样做，这样我们就可以删除重复的数字。
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > res;
std::sort(num.begin(), num.end());
for (int i = 0; i < num.size(); i++) {
int target = -num[i];
int front = i + 1;
int back = num.size() - 1;
while (front < back) {
int sum = num[front] + num[back];
// Finding answer which start from number num[i]
if (sum < target)
front++;
else if (sum > target)
back--;
else {
vector<int> triplet = {num[i], num[front], num[back]};
res.push_back(triplet);
// Processing duplicates of Number 2
// Rolling the front pointer to the next different number forwards
while (front < back && num[front] == triplet[1]) front++;
// Processing duplicates of Number 3
// Rolling the back pointer to the next different number backwards
while (front < back && num[back] == triplet[2]) back--;
}
}
// Processing duplicates of Number 1
while (i + 1 < num.size() && num[i + 1] == num[i])
i++;
}
return res;
}
既然你要求改进，那么这个算法如何:
创建一个std::unordered_map<int, int>，将每个输入映射到出现的次数。然后:
for (const auto & it = map.begin(); it != map.end(); ++it) {
for (const auto & it2 = it; it2 != map.end(); ++it2) {
auto it3 = map.find(-*it - *it2);
if (it3 != map.end()) {
it ((*it > *it3) || (*it2 > *it3)) continue;
if (it == it2) {
if (it == it3) {
if (it.second > 2) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
} else {
if (it.second > 1) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
}
} else if (it2 == it3) {
if (it2.second > 1) cout << *it << ", " *it2 << ", " << *it3 << std::endl;
} else {
cout << *it << ", " *it2 << ", " << *it3 << std::endl;
}
}
}
}
应该是没有重复的O(n^2)。
我确实解决了这个问题，但它效率低下，并且在一些测试用例中超出了时间限制。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums) {
/*
* If less than 3 elements are passed return empty vector
*/
if (nums.size() < 3)
return {};
int target = 0; // all three numbers sum up to 0 as given
vector<vector<int>> outer; // this is returned by the function
unordered_multimap<int, vector<int>> umap; // unordered_map for keeping sum and indices
/*
* Calculate sum of each pair of numbers
* Store the sum as key and the pair as value
* i != j is guaranteed
*/
for (int i = 0; i < nums.size(); i++)
for (int j = i + 1; j < nums.size(); j++) {
vector<int> temp;
temp.push_back(i);
temp.push_back(j);
umap.emplace(make_pair(nums[i] + nums[j], temp));
}
/*
* Go through each element and calculate the difference
* between target and that element, this gives the sum
* of the other two elements.
* Look for the sum in unordered_map
* If it is present check if all three indices are not equal to each other
*/
//unordered_set<vector<int>> uset;
for (int i = 0; i < nums.size(); i++) {
vector<int> inner;
int diff = target - nums[i];
auto it = umap.find(diff);
while (it != umap.end()) {
inner = it->second;
if (it != umap.end() && i != inner[0] && i != inner[1]) {
inner.push_back(i);
//vector<int> tmp;
//for (auto &j: inner)
// tmp.push_back(nums[j]); // push actual numbers instead of indices
//sort(tmp.begin(), tmp.end()); // sort the inner three elements
//if (find(outer.begin(), outer.end(), tmp) == outer.end()) // for removing duplicates
outer.push_back(inner);
}
umap.erase(it);
it = umap.find(diff);
}
}
for (auto &i: outer)
for (auto &j: i)
j = nums[j];
//sort(i.begin(),i.end());
set<vector<int>> uset;
for (auto &i: outer) {
sort(i.begin(), i.end());
uset.insert(i);
}
outer.clear();
outer.insert(outer.end(), uset.begin(), uset.end());
return outer;
}
int main() {
vector<int> v{-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
vector<vector<int>> ret = threeSum(v);
for (auto &i: ret) {
for (auto j: i)
cout << j << " ";
cout << endl;
}
}
var nums = [-1, 0, 1, 2, -1, -4];
// var nums = [0, 0, 0];
var threeSum = function (nums) {
var result = [];
if (nums.length > 3) {
for (var i = 0; i < nums.length; i++) {
for (var j = 2; j < nums.length; j++) {
for (var k = 4; k < nums.length; k++) {
if (i != j && i != k && j != k) {
if (nums[i] + nums[j] + nums[k] == 0) {
var ans = [nums[i], nums[j], nums[k]];
result.push([...ans]);
}
}
}
}
}
return result;
} else if (nums.every((item) => item === 0)) {
result = [[...nums]];
return result;
} else {
result = [];
return result;
}
};
console.log(threeSum(nums));