在采访中得到这个。这个问题与非常著名的问题非常相似 Find a triplet that sum to a given value , 略有不同。这里我们要打印ALL 三胞胎,而不仅仅是一个。
数组可以包含重复项。
例如考虑以下数组:
[1, -1, 2, 0, -2, 4, -2, -2, 4]
输出应该是:
[1, -1, 0]
[4, -2, -2]
[2, -2, 0]
三元组的顺序或三元组中数字的顺序并不重要。
使用排序或使用集合有 n^2 个解决方案(如上面链接中的解决方案)。但是如何确保我们只打印唯一的三元组呢?我能想到的一个解决方案是使用一组来跟踪我们目前看到的三胞胎。但不确定这是否是最好的方法,或者是否有其他解决方案使用排序等来生成独特的三元组。
最佳答案
这没什么不同。只有当我们有重复项时,我们才需要在每个级别上跳过它们,所以 std::set
不一定。
#include <vector>
#include <algorithm>
#include <iostream>
#include <array>
int main()
{
const int kDesired = 0;
std::vector<int> a = { 1, -1, 2, 0, -2, 4, -2, -2, 4 };
std::sort(a.begin(), a.end());
std::vector<std::array<int, 3>> triples;
for (int i = 0; i < (int)a.size(); ++i) {
const int others = kDesired - a[i];
for (int j = i + 1; j < (int)a.size(); ++j) {
for (int k = (int)a.size() - 1; k > j; --k) {
if (a[j] + a[k] == others) {
triples.push_back({ { a[i], a[j], a[k] } });
}
else if (a[j] + a[k] < others) {
break;
}
// we don't want a[k] to be the same next time
while (j + 1 < k && k < (int)a.size() && a[k] == a[k - 1]) --k;
}
// we don't want a[j] to be the same next time
while (i + 1 <= j && j < (int)a.size() - 1 && a[j] == a[j + 1]) ++j;
}
// we don't want a[i] to be the same next time
while (0 <= i && i < (int)a.size() - 1 && a[i] == a[i + 1]) ++i; }
for (const auto& t : triples) {
std::cout << t[0] << " " << t[1] << " " << t[2] << std::endl;
}
return 0;
}
-2 -2 4
-2 0 2
-1 0 1
关于algorithm - 找到所有总和为零的唯一三元组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52677527/