c++ - 有人可以帮助我解决求和为k的数组元素对索引的问题吗？

Question

#include <vector>
#include <iostream>
#include <unordered_map>

int main() {

    std::unordered_map<int, int> nMap;

    int a[] = {3,4,5,6,5,7,4};
    int k = 10;
    for(int i = 0; i < 7; i++) {
        int rem = k - a[i];
        if(nMap.find(rem) != nMap.end()){
            printf("(%d,%d)\n",nMap[rem], i);
        }

        nMap.insert(std::pair<int,int>(a[i],i));
    }   
    return 0;
}

在上面的程序中，我使用了哈希图来查找给出总和等于k的元素对的索引。对于上面的代码，它工作正常，并给了我所需的对

(1,3)
(2,4)
(0,5)
(3,6)

注意:这些是实际加到k的元素的索引。

但是，这对于输入 int a[] = {1,1,1,1,1,1,1}; int k = 2确实可以正常工作，给出的输出是:

(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(0,6)

但是据我估计输出必须具有所有对，即(1,2)，(1,3)...(5,6)。
解决上述问题的正确程序是什么？

Answer 1

输入1,1,1,1,1,1,1产生6 + 5 + 4 + 3 + 2 + 1 = 21 = N *(N-1)/ 2 =N²/ 2-N / 2输出:

(0，1)
(0，2)
(0，3)
(0，4)
(0，5)
(0，6)
(1、2)
(1，3)
(1，4)
(1、5)
(1，6)
(2、3)
(2、4)
(2、5)
(2、6)
(3，4)
(3、5)
(3，6)
(4、5)
(4、6)
(5、6)

您需要一个复杂度为O(N²)的算法来产生这样的输出。您的代码不起作用，因为复杂度为O(N)的代码无法产生这么多的输出。

这是使用无序映射的更高效的解决方案:

#include <array>
#include <vector>
#include <iostream>
#include <unordered_map>

int main() {
    std::array<int, 7> a{3,4,5,6,5,7,4};
    std::unordered_map<int, std::vector<std::size_t>> nMap;
    for (std::size_t i = 0; i < a.size(); ++i) {
        nMap[a[i]].push_back(i);
    }
    int k = 10;
    for (const auto &el : nMap) {
        if (nMap.find(k - el.first) == nMap.end()) continue;
        for (const auto &left : el.second) {
            for (const auto &right : nMap.at(k - el.first)) {
                if (left < right) std::cout << '(' << left << ',' << right << ")\n";
            }
        }
    }
    return 0;
}

我用一个值的所有索引填充了 map 。现在，我可以访问O(1)中的所有索引以获取目标值。我迭代 map 中的所有值并打印所有成对的值。