算法题求解-Two Sum的延伸

今天想起来一道春招实习的面试题目,当时没有写出来,后来就不了了之了,今天突然想起来这题,感觉看似简单,又有很多坑,所以发出来看看大家有没有什么好的解法:
题目: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数的索引组合有多少对?数组中的元素有重复。
nums = [1, 1, 2, 3, 3, 3, 3, 4, 4, 5, 6]
target = 6
共有10组解
--------------------------------------
下面有大佬提到了hash统计次数,我这边实现过了,的确简单方便。
至于双指针的,我觉得楼下大佬可以实现下,参考下,我之前就是一直想用双指针实现,但是没办法AC。
#笔试题目##春招#
全部评论
leetcode上的题。 先排序,使用两个指针遍历就好
点赞 回复 分享
发布于 2019-07-01 23:06
用个unordered_map存一下那些数字,每次找a[target-a[i]存不存在。存在加上a[i],以元素值为键值,次数为实值
点赞 回复 分享
发布于 2019-07-01 20:19
动态规划: for(int n: nums){     dp[i] += dp[i -n]; }
点赞 回复 分享
发布于 2019-07-01 20:26
没排序的话就Backtracking吧
点赞 回复 分享
发布于 2019-07-02 14:31
Java的话 可以利用hashMap,这样子的时间复杂度是O(n), 之前有想过使用双指针, 但是失败了。。
点赞 回复 分享
发布于 2019-07-02 13:19
这题双指针貌似不行,因为得到一个结果不管移动左指针还是右指针结果都会少,和 4SumII 类似用的map,还是同桌强啊 public int twoSum(int[] numbers, int target) { //保存结果数 int cnt = 0; //key 存数值,value 存当前值出现的次数 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) { cnt += map.get(target - numbers[i]); } map.put(numbers[i], map.getOrDefault(numbers[i], 0) + 1); } return cnt; }
点赞 回复 分享
发布于 2019-07-02 11:24
就这种题感觉就是面试一紧张会写不出来。我觉得应该是基本的hash记录吧,楼其他上大佬说的都看不懂
点赞 回复 分享
发布于 2019-07-02 09:56
排序好的数组那还是双指针,注意特判一下
点赞 回复 分享
发布于 2019-07-01 22:58
两个指针分别从前后遍历,和大了后面的指针前移,小了前面的指针后移
点赞 回复 分享
发布于 2019-07-01 21:14
遍历每一个值,统计一下目标值减去遍历值的个数,没有就为0
点赞 回复 分享
发布于 2019-07-01 21:12
hash记录每个数字出现的次数就好了。
点赞 回复 分享
发布于 2019-07-01 20:15

相关推荐

昨天 18:27
已编辑
门头沟学院 C++
26学院本太难了,很多公司机筛就给我刷了。机会都难拿到如果是简历存在问题也欢迎拷打————————————————————分割线——————————————————————2026.3.4更新:发完贴之后,时不时投递又收到了不少的笔试/面试邀请。主要是之前投递简历出去之后基本上都是沉默状态,年后好转了不少timeline:2026.01.21&nbsp;文远知行笔试,半年多没刷算法题&nbsp;-&gt;挂&nbsp;(后续HR说春招可以重新安排笔试)2026.2.4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;小鹏汇天&nbsp;技术一面,第二周收到结果&nbsp;-&gt;挂2026.2.12&nbsp;&nbsp;&nbsp;大众Cariad代招&nbsp;技术二面&nbsp;-&gt;Offer2026.2.28&nbsp;&nbsp;&nbsp;多益网络技术面试,由于风评太差,一直在犹豫要不要接面试&nbsp;-&gt;推迟-----------分割线-----------2026.3&nbsp;月前的某一天,临时去电网报名了二批计算机岗位的笔试2026.3.6&nbsp;从上家公司实习离职,氛围最好的一家公司,leader&nbsp;说可以帮忙转正,但是流程太长,而且我们部门据说只有一个&nbsp;hc,更想要研究生,我很有可能是会被签外包公司在这里干活,就离职了。2026.3.9&nbsp;入职新公司,大众Cariad&nbsp;以外部公司的身份进组,项目组签了三年,后续三年应该都可以在这里呆,不知道有没有希望原地跳槽。2026.3.10&nbsp;电网考试居然说我通过资格审查了,短信约我去参加资格审查,请假一天,买了&nbsp;12&nbsp;号晚上的机票回成都2026.3.15&nbsp;参加国家电网三新计算机类的笔试2026.3.17&nbsp;电网出成绩了,感觉很低。觉得已经🈚️了2026.3.18&nbsp;收到电网面试通知,通知&nbsp;3.22-3.25&nbsp;这个时间去面试,我的岗位只招&nbsp;1&nbsp;个人。据说面试只有&nbsp;2-3&nbsp;人,不知道能不能成功
点赞 评论 收藏
分享
评论
点赞
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务