登录
  • #码农类general
  • #amazon
  • #工作信息
  • #求职
  • #找工就业

amazon two sum with duplicates

liudaisuda
10556
7
请教筒子们,那个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点, 所以再来抱抱佛脚。
7条回复
热度排序

发表回复