c++ - 数组中元素的组合返回总和

Question

我正在使用数据结构学习优化问题。

为此，我考虑了一个手头的问题。

我有一个像这样的数组:movies[] = { 2,3,4,5,6,7,2,4,9 }

我有一个总和值:k = 5

现在我找到返回 "k" 的数组元素的组合例如:

2 + 3 = 5
3 + 2 = 5

下面的代码可以做到这一点:

#include<iostream>
#include<tuple>
using namespace std;

std::tuple<int, int> movies_combo(int k,int movies[]) {
    int value_1 = 0, value_2 = 0;
    int size = sizeof(movies);

    //First lets sort the array in ascending order
    //For optimized solution
    double mid = sizeof(movies) / 2;

    //Second lets find the sum of combination of array elements which gives "k"
    for (int i = 0; i < (size-1); i++) {
        for (int j = 0; j < (size - 1); j++) {
            if (movies[i] + movies[j] == k) {

                cout << "The two movies are: " << movies[i] << "and" << movies[j] << endl;

            }
        }
    }
    return make_tuple(value_1, value_2);
}

int main() {
    int movies[] = { 2,3,4,5,6,7,2,4,9 };
    int k = 6;
    int value_1, value_2;

    tie(value_1,value_2) = movies_combo(k, movies);

    //cout << "The two movies are: " << value_1 << "and" << value_2 << endl;
}

现在我的时间复杂度是 O(n^2)。

我可以通过在开始时对数组进行排序并消除值 > k 来进一步降低复杂性。但这仅在几个场景中有用，而不是优化的一般解决方案。

我希望有一些数据结构和算法方法可以在这种情况下非常方便地降低对数级别示例的复杂性:nlogn 或 logn。

如果有人对降低时间复杂度有任何想法，请告诉我。

Answer 1

您可以在 O(nlogn) 甚至更好的 O(n) 时间内完成此操作。

O(nlogn) 方法:

1.在O(nlogn)时间内对元素进行排序

2。对于每个元素movies[i]，应用 binary search 在数组中从位置 i+1 到数组末尾搜索元素 k - movies[i]。

3。如果找到，您就有了元组，因为 movies[i] + (k - movies[i]) = k

O(n) 方法:

1.将所有元素存储在哈希表中。

2。对于每个元素 movies[i]，在哈希表中搜索 k - movies[i]，如果找到你的元组.

3。由于在哈希表中搜索需要 O(1) 时间，因此这种方法需要时间 O(n)。