3Sum without sorting

看fb面经看到这道题，感觉应该用HashMap，不过自己写不出来，所以来问问各位。
要求还是O(n^2)

必须先排序，然后把3sum的问题改为给定一个值的2sum的问题。去重只需要在遍历的时候不重复处理同一个值就好。比如

1 2 2 2 2 4 6 9 。。。

当处理完第一个二的2sum的问题后，下一个要处理的是给定4的2sum的问题。

红茶香槟可乐 发表于 2018-3-5 13:34
求啥啊 是求全部的解吗，
for 外层， 用set防止外层重复
内循环一遍 hashmap

这样最后还是有重复的，[-1,0,1,2,0,-1,-4] 会有[-1,-0,1],[1,0,-1]. 还不知道要怎么解决这个问题。

顶一下，之前帖子审核了两天。。。

hash的key是两个数的和，value是 两个index，

然后再扫一遍，看能不能凑出来。

--

但是有重复的话，去重比较麻烦。

感觉还是sort好用

感觉可以先数组去重。 然后接着用3sum里那样的写法就行了？

关注一下这个问题

要求without sorting 咋做到O（n^2）0 0 关注 求指教

不排序的难点就是去重，最简单的就是先统计所有在nums里面出现的数字和次数。
假设你有 a b c 三个数是potential 的答案之一，所以 a, b 可能是 nums里面任何一个数(a,b可能相等)。
因此两个for loop 就可以找到所有的a, b 的可能，c可以通过 -(a+b) 计算出来。
for( a = any num in distinct nums)
    for( b = any num in distinct nums)
          c = -(a +b)
这样一来， a, b, c的值我们都得到了，两个for loop搞定就是O(k^2); 这个k是nums里面distinct的num的个数。
之后就开始玩去重。 去重有很多方法，你自己可以定义。
比如你可以规定 a <= c <= b来防止 a,b,c ; c,b,a ; b,a,c 这种重复
具体还有些小trick 自己实现下看看
总的complexity 是  O(n) + O(k^2)  ； O(n)是遍历一遍nums 来统计，O(k^2)是来生成potential answer，在加入final answer list前要筛选。
这个答案比O(n^2)好一些

bowenf 发表于 2017-10-28 02:58
感觉可以先数组去重。 然后接着用3sum里那样的写法就行了？

这样不对吧～ 那[0,0,0] target==0的这种不就miss了吗

求啥啊 是求全部的解吗，
for 外层， 用set防止外层重复
内循环一遍 hashmap
然后two sum， 一旦找到俩数就把俩数放进内层用的hashset里，用set来防止重复情况发生？