15.三数之和

给定一个整型向量，找出所有的三元组使之和为0（不允许重复）。

思路1：第一反应是一道动态规划问题。如果采用三层循环来查找的话，复杂度会达到n^3，这也许能完成一两次操作，但应该无法通过提交。事实上，三个数相加为0，必定有一个大于0和一个小于0的数字，应当能节省部分时间。是否可以转换成在两个数组中，寻找出一个数，使得另一个数组中存在两数之和相等？这就变成了第一题。只要在外圈再套一层循环就好了。

ps 这里又出现了一个问题，0怎么办？假设存在三个0，则0 0 0应当是一种情况。目前的解决方案是认为0既是正数又是复数。 利用find函数，寻找到第一个0，并将其归入到neg中，剩下如果有多的0都归入pos。

pps 如何防止重复呢？假设存在1 1 1 -2 如果我们单纯的寻找，那么肯定会认为三个1是不同的1，实际上只要把多于三个的重复数字都消减到两个即可（注意0除外！！！）。

这样看下来，这个方法的前置准备工作是不是过多了点？况且，每一个数都要建立一个map 对内存的开销也比较大。

思路2：利用指针，第一步还是一样需要对原先的数组进行排序。利用 i l r 三个指针来表示三元组。如果指针 i 指向了相同的值，则直接跳过后面的值， 如1 1 1 时，我们只考虑第一个1。l指向i之后，r指向末尾，将三者相加，判断和的大小，如果和大于0 则r需要前移，反之l后移，如果刚好为0就存着。但是要注意，如果l 和 r 有多个重复值那么我们就得跳过他们才行。还要注意的一点是 0 0 0 时，如果我们l r 都存完了，但是此时l 和 r 的附近还是相同的，如果再继续 l++ 则这时候l就指向最后的0的，再判断立马溢出。同理 r 也要判断。

如歌不加大小判断，l 到最后一位后，没法继续判断循环条件了。 为了可读性的考量，改成了 l 和 r 的范围判断