算法题求解-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

相关推荐

Vincent777...:实习经历可以考虑放上去,对于软件使用方面可以细化一些,比如调整为:熟悉基于LSDYNA的瞬态动力学仿真分析,熟悉基于WORKBENCH的结构拓扑优化
我的简历长这样
点赞 评论 收藏
分享
评论
点赞
7
分享

创作者周榜

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