amazon two sum with duplicates

请教筒子们，那个Amazon 的经典two sum with all pairs 的题目(preserve duplicate pairs) 应该怎么处理?  比如说｛1， 2， 2， 3｝， target = 5, 他要｛（2，3）， （2， 3）｝ 怎么办？
我目前只想到hashmap 的方法，就是一个hashmap 存数字，和对应出现的个数， 再用一个array 来存distinct elements. Sort 这个aux array, 根据two pointer 来找到符合sum = target 的pair, 然后再把这个pair添加m*n 次（m 是 element A出现的次数， n是element B出现的次数）

请问这个思路对吗？ 还有没有别的方法？

P.S. Amazon的phone interview 约定时间过了一个小时，recruiter 打电话说改在下午4点， 所以再来抱抱佛脚。

抱歉 发了个无用贴。 如果是如下情况 至少要O(N^2)： {1， 1， 1， 1， 1} target=2.

先过一遍,hashmap存<key,value>-><2,[1,2]>对应index

kurtwang 发表于 2015-3-6 02:40
先过一遍,hashmap存->对应index

然后是再过一遍array, 搜索target-array[i]是否在map中？

liudaisuda 发表于 2015-3-6 02:43
然后是再过一遍array, 搜索target-array是否在map中？

是的。。或者过一遍map也可以,把算过的记录到set里,不过其实care duplicate的话最差就是n^2了。。

感觉用个hashmap就行了吧 key 是每个element,value 是每个元素的个数。然后历遍这个hashmap 输出所有的组合？

timpark4 发表于 2015-3-6 03:59
感觉用个hashmap就行了吧 key 是每个element,value 是每个元素的个数。然后历遍这个hashmap 输出所有的组合 ...

嗯，如果要求数值的话，只要存个数就可以。

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南