3 sum

看地理帖子上说A的面试问了3sum的hashmap和不hash的做法，求问各位大神不hash怎么做呢？

遍历最小的number，对比它大的数做不用hash的two-sum，就是从两头往中间扫，线性时间的。

convert it to 2sum which is O(n)

把第一个数选好后，剩下的部分从两头往中间扫即可

。。。这个题目。。。歧义不小

那hash怎么做呢。。以前都是不hash做的。。

不论hash与否，关键都是为了查重。

比如这样一个数组 1 2 2 3 4，target是 7， 那么在sort好之后，a = 1, b = 靠左的2，c = 4，这是一个解；找到这个解之后需要把b的位置向右移动，c的位置向左移动。
问题在于，移动c和b的时候要保证，在移动之后，b和c不能还都是原来的值。这个就是不用hash的做法的关键：它会让b往右移动两位直到找到下一个不是2的数，也就是3。这样才能保证不会最终的结果里面没有重复。

用hash的做法就不用担心这个问题，因为hashset本身就可以用来查重。每次找到一个解就看hashset里面这个解有没有出现过，没出现过就放到最终解里面，出现过了就不放了。