在使用散列 table 解决两个和问题时，如何计算重复值？

Question

假设我有一个经典的二和问题，但有一点不同

如果给我一个整数列表和目标

我需要打印所有加起来等于总和的值对

不重复对称值

不重用值

出于明显的原因，我试图避免使用蛮力方法，但是如果我实现一个散列映射，每个值作为键，元素是原始数组中该值的频率。如何让算法只打印一次每个值对？

function findPairs(arr, target){

  let hashMap = {};

  let results = [];

  for(let i = 0; i < arr.length; i++){
    if(hashMap.hasOwnProperty(arr[i])){
      hashMap[arr[i]]++;
    }else{
      hashMap[arr[i]] = 1;
    }
  }

  for(let i = 0; i < arr.length; i++){

    let diff = target - arr[i];

    if(hashMap.hasOwnProperty(diff) && hashMap[diff] > 0){ 
        results.push([arr[i], diff]);
        hashMap[diff]--;
    }
  }

  console.log(results);

}

findPairs([1, 3, -1, 11, 7], 10);
findPairs([5, 5, 5, 5, 5], 10);

findPairs([1, 3, -1, 11, 7], 10)

(3, 7) (-1, 11)

findPairs([5, 5, 5], 10)

(5, 5)

findPairs([5, 5, 5, 5], 10)

(5, 5) (5, 5)

findPairs([5, 5, 5, 5, 5], 10)

(5, 5) (5, 5)

findPairs([5, 5, 5, 5, 5, 5 ], 10)

(5, 5) (5, 5) (5, 5)

Answer 1

据我了解，这是问题的摘要：

您的数组可以有重复的元素，例如：- [1, 2, 3, 2, 4]

您想将 [4, 1, 2, 3, 2, 4] 打印为 (2, 4), (2, 4)

vector<pair<int, int> > findPairs(vector<int> arr, int target){
    int size = arr.size();
    map<int, int> hashMap;

    for(int i = 0; i < size; i++){
            // C++ map assigns 0 as default if the key is not present, C++ map uses Red Black Tree 
            if(hashMap[arr[i]] == 0)
                    hashMap[arr[i]] = 1;
            else
                    hashMap[arr[i]]++;
    }
    /** Use to store result in (int, int) form
     *  Vector is a Dynamic array
     */
    vector<pair<int, int> > results;
    for(int i = 0; i < size; i++){
            int diff = target - arr[i];
            hashMap[arr[i]]--;
            if(hashMap[diff] >= 1)
                    results.push_back(make_pair(arr[i], diff));
            hashMap[diff]--;
    }
    return results;

}

此代码基于您在问题中提供的示例。

在使用散列 table 解决两个和问题时，如何计算重复值？

How do I account for duplicate values when solving the the two sum problem using a hash table?

algorithm

big-o

hashtable

hashmap