c*********t
发帖数: 2921 | 1 看到最近有人问4sum的问题，
可是我想如果能对2sum ,3sum的问题弄透了，各种方法都研究一下，4sum应该就是一个
扩展，对吧。
我们能不能先列一下可以解决2sum的所有方法？假设数组中有重复的数。
有种方法是用hashtable,可是我发现有个问题，
比如给定数组 [ 1 2 3 4 5 6 7 8 9],求出之和为 10 (target)的两个数，
用hashtable,我们可以得到
1 9
2 8
3 7
4 6
5 5 <<<<<<<这里好像不对了，因为数组里只有一个5,这个问题该如何处理？
6 4
7 3
8 2
9 1
另外就是得出的组合有重复的，象 1 9, 其实和 9 1 是一回事，该怎么办？
还有哪些常用的方法来解决2sum问题的？
谢谢！ | y*d
发帖数: 2226 | 2 3sum的思路可以用于2sum，但是用在2sum上就是脱了裤子放屁
因为2sum有1万种解法都是nlogn的
4sum也许有更神奇的解法
我知道的就是在3sum基础上再乘n | t*********n
发帖数: 89 | 3 2sum,如果用hash table的话，循环中每一次查元素都只在已有的hash table 查，比如
1 -> 此时 hash table为空，则无结果
2 -> 此时 hash table 里有仅有1， 无结果
....
9 -> 此时 hash table 里有{1，2，3，..8},查到1，成立
对于duplicate,我的想法是在hash_table的value以一个bool来表示是否已经用过，即
hash_table myhash。比如数组为{5，5，5}，目标是10
5-> 此时hash table为空，无结果
5-> 此时hash table里面有5，标记myhash[5] = false;
5 -> 此时hash table里面虽然有5，但是myhash[5] = false,则不成立。
请问下大家有没有更巧的方法？ |
|
