算法题（32）：三数之和

审题：

需要我们找到满足以下三个条件的所有三元组，并存在二维数组中返回

1.三个元素相加为0

2.三个元素的下标不可相同

3.三元组的元素不可相同

思路：

混乱的数据不利于进行操作，所以我们先进行排序

我们可以采取枚举的方法进行解题

首先最容易想到的就是三个for循环， 每个循环确定一个元素，遍历后在最深的第三层循环进行判断，如果满足相加为0就把对应数据存入二维数组

不过根据第二点：三个元素的下标不可相同

我们需要避免出现一个三元组中同一个位置的元素被用两次

（eg：nums[0] nums[0] nums[1]）

有：

a（第一层循环的元素下标）< b（第二层循环的元素下标）< c（第三层循环的元素下标）

不过此时我们的时间复杂度有点高：O（N^3） 如何优化？

假设num1,2,3分别是三元组的值，有num1+num2+num3 = 0

我们先定住num1不变，num2越大，num3就越小，也就是说我们可以让第三层循环从n-1开始，从右向左循环，这样子可以更快找到满足条件的值

此时第二三层循环的时间复杂度就变成了O（N），我们此时可以换一种方法写后面两层循环

这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法。

总结一下，遍历方法为：第一层循环+双指针（代替第二三层循环）

解题：

（1）预处理

（2）第一层循环

第一层循环的作用是确定第一个元素值，且根据第三点我们不能有重复数据，一旦当前的值和前一个是一样的，则直接continue到下一个索引位置

（3）双指针

目标条件判断方法:由于已经确定了第一个元素的值，所以根据三者之和为0可以得知后面两个元素之和为-num1即为满足条件

遍历过程中，若满足条件就把元素插入二维数组，插入后移动双指针（因为此前移动过left和right，所以要再满足left < right的条件），移动后判断是否满足和前一个元素不同的条件，不满足就循坏更新直到满足。

若不满足条件

和大于target，要让和变小，right--

和小于target，要让和变大，left++

最后返回answer即可

15. 三数之和 - 力扣（LeetCode）