给定一个整型向量,找出所有的三元组使之和为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 也要判断。