c - 从 3 个数组中找出 3 个数字 a、b、c，其总和等于给定数字 T？

Question

这是一道面试题，所需的复杂度是 O(nlogn)。我实现了 O(n^2 logn) 的解决方案。 假设解决方案存在。 也请提供您的解决方案的伪代码。 谢谢。

我的 O(n^2 logn) 解决方案的代码片段:

triplet SumOf3(vector<int> A, vector<int> B, vector<int> C, int T)
{
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    for (int i = 0; i < A.size(), ++i) {
        for (int j = 0; j < B.size(); ++j) {
            int s = A[i] + B[j];
            int ind = int(lower_bound(C, C + C.size(), T - s) - C.begin());
            if (s + C[ind] == T) {
                triplet ans;
                ans.a = A[i];
                ans,b = B[j];
                ans.c = C[ind];
                return ans;
            }
        }
    }
}

Answer 1

我不明白你的问题是函数返回 bool 值还是三个数字。 我认为应该嵌套 3 个 for 循环，为什么要在数组 C 中搜索数字 T。 你只需要看看总和是否等于数字 T 以及 C 中的另一件事，我们没有像 .length 这样的东西。 这是一个例子:

int temp;
for(int i = 0;i<A.length;i++)
  for(int j = 0;j<B.length;j++)
    for(int k = 0;k<C.length;k++)
        temp = A[i]+B[j]+C[k];
        if(temp==T)
        return true;
return false;