哈希映射来查找与给定总和相加的对

Question

我正在尝试学习如何在 C++ 中使用哈希映射，但无法将随机生成的数组放入哈希映射中，其中键的整数和向量作为值（对于数组中的重复值）。我还没有开始对总和进行编码，因为我想确保我可以先将数组输入到哈希图中。

当我使用显示函数输出哈希图时，我得到

        Total size: 1
 Index in H  Number
key: 0  values: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

我创建的数组有15个值，范围为1-10，因此存在重复，因此需要向量。我不确定我做错了什么，所以欢迎任何形式的指导。

#include <iostream>   
#include <time.h>     
#include <fstream>
#include <map>
#include <cstdlib>
#include <iomanip>
#include <vector>

void display(std::map <int, std::vector<int> > hash);

int main(){
    srand (time(NULL));
    int temp;
    int tempCount = 1;
    int count = 0;
    int number;
    int k = 10; //sum for pairs in an array

//create array for testing
    int size = 15;
    int foo[size] = {};
    for(int i = 0; i < size; ++i){
        foo[i] = ((double)rand() * (10 - 1) / (double)RAND_MAX + 1);
    }
    //print array:
        for(int i = 0; i < size; ++i){
        std::cout << foo[i] << std::endl;
    }

//Find pairs in an array whose sum is equal to ten using hash map    
    std::map <int, std::vector<int> > hash;
    const std::pair<int, int> pairs[size];
    for(int i = 0; i < size; i++){
        std::make_pair(pairs[foo[i]] , i);
    }

    const int N = sizeof(pairs) / sizeof(pairs[0]);
    for(int i = 0; i < N; ++i){
        const int& key = pairs[i].first;
        const int value = pairs[i].second;
        hash[key].push_back(value);
    }
    display(hash);
}

void display (std::map <int, std::vector<int> > hash)
{
    std::cout << "\tTotal size: " << hash.size() << std::endl; /* Output the size */
    /* Create an iterator, much like vector iterators */
    std::map <int, std::vector<int> >::iterator it;
    for (it = hash.begin(); it != hash.end(); it++){
        /* Output first (which is index) and second (which is the element) */

        const int& key = it->first ;
        std::cout << "key: " << key << "  values: ";

        const std::vector<int>& values = it->second ;
        for(std::size_t i = 0; i < values.size(); ++i)
            std::cout << values[i] << ' ';
        std::cout << '\n';
    }

    std::cout << std::endl; /* Print a new line */
}

Answer 1

通过改变：

const std::pair<int, int> pairs[size];
    for(int i = 0; i < size; i++){
        std::make_pair(pairs[foo[i]] , i);
    }

致：

std::pair<int, int> pairs[size];
    for(int i = 0; i < size; i++){
        pairs[i] = std::make_pair(foo[i] , i);
    }

应该解决最初的问题。

注意：我删除了 const，以便可以修改对值，否则它们都将保留 (0,0)。

Answer 2

STL 映射适用于每个键都有唯一值的情况。 使用多重映射比使用向量来保存多个结果要容易得多。 我修改了您的代码以演示其用法。 此代码需要 c++11，但即使您使用较旧的编译器，仍然可以使用多重映射。

#include <iostream>
#include <time.h>
#include <map>
#include <cstdlib>

using namespace std;

int main()
{
    srand ((unsigned int)time(NULL));

    //create array for testing
    constexpr int size = 15;
    int foo[size];
    for (int i = 0; i < size; i++)
    {
        foo[i] = ((double)rand() * 10 / (double)RAND_MAX + 1);
    }

    //print array:
    for(int i = 0; i < size; ++i)
    {
        cout << foo[i] << endl;
    }

    //Find pairs in an array whose sum is equal to ten using hash map
    multimap<int, pair<int, int>> sums;
    for (int i = 0; i < size; i++)
    {
        for (int j = i+1; j < size; j++)
        {
            int sum = foo[i]+foo[j];
            sums.insert(make_pair(sum, make_pair(foo[i], foo[j])));
        }
    }

    // Print the pairs that sum to 10.
    const auto from = sums.lower_bound(10);
    const auto to = sums.upper_bound(10);
    for (auto i = from; i != to; i++)
    {
        cout << i->second.first << " + " << i->second.second << " = " << i->first << endl;
    }
}

Answer 3

嘿，我看到了 Random Number(2015 年 7 月 8 日) 写的解决方案。即使我们使用 MultiMAp，获取总和为 10 的对的时间复杂度仍然是 O(n^2) 。那么它是如何解决我们的问题的呢。我们可以在没有 Hashmap 的情况下对其进行编码，然后只需使用简单的 Algo。