首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在使用哈希表解决两个和问题时,如何考虑重复的值?

在使用哈希表解决两个和问题时,如何考虑重复的值?
EN

Stack Overflow用户
提问于 2019-03-28 05:38:53
回答 1查看 1K关注 0票数 1

假设我有经典的两个求和问题,但有点扭曲

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

我需要打印与和相加的所有值对。

不重复对称值

而不重用值

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

代码语言:javascript
复制
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,10)

(5,5) (5,5)

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-03-28 08:57:17

就我所知,这是问题的摘要:

  • 数组可以有重复的元素,例如:- 1,2,3,2,4
  • 您要打印副本4,1,2,3,2,4作为(2,4),(2,4) vector >findPairs(向量arr,int目标){ int size = arr.size();map hashMap;for(int i= 0;i< size;i++){ // C++映射指定0作为默认值,如果键不存在,C++映射使用红色黑树if(hashMap[arri] == 0) hashMap[arri] = 1;} /**用于存储( int,int)表单*向量是一个动态数组*/ vector >结果;for(int i= 0;i< size;i++){ int diff = target - arri;hashMap[arri]-;if(hashMapdiff >= 1) results.push_back(make_pair(arri,diff));返回结果; }

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

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55390811

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档