算法题求解-Two Sum的延伸

leetcode上的题。 先排序，使用两个指针遍历就好

用个unordered_map存一下那些数字，每次找a[target－a[i]存不存在。存在加上a[i]，以元素值为键值，次数为实值

动态规划： for(int n: nums){     dp[i] += dp[i -n]; }

没排序的话就Backtracking吧

Java的话 可以利用hashMap，这样子的时间复杂度是O(n), 之前有想过使用双指针, 但是失败了。。

这题双指针貌似不行，因为得到一个结果不管移动左指针还是右指针结果都会少，和 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; }

就这种题感觉就是面试一紧张会写不出来。我觉得应该是基本的hash记录吧，楼其他上大佬说的都看不懂

排序好的数组那还是双指针，注意特判一下

两个指针分别从前后遍历，和大了后面的指针前移，小了前面的指针后移

遍历每一个值，统计一下目标值减去遍历值的个数，没有就为0

hash记录每个数字出现的次数就好了。