leetcode三数之和题目

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

题目难点：

1. 如何去除重复解？

2. 如何降低时间复杂度？

答案：排序加双指针

这里记录一下我的思考过程。

排序的主要目的是消除重复解，并且为使用双指针做铺垫。下面进行具体分析。

1. 例如题目所给示例[-1 0 1 2 -1 -4]，当我们针对第一个-1进行分析之后，就没必要对第二个-1进行分析了，因为对相同的元素进行分析得到的解必是重复解。而在排序之后，我们很容易完成这个步骤，只要判断前后两个元素是否一样即可，如果一样就跳过该次循环，通过这个方法，我们消除了一部分重复解。

2. 排序为使用双指针做了铺垫。我们可以将三数之和转换为两数之和。我们固定当前位置为\(i\)，\(i\)位置上的值为\(nums[i]\)，那么我们只要在\(i+1\)到\(n\)的位置上寻找两个数加起来为\(-nums[i]\)即可。我在这里产生了疑问，为什么是在\(i+1\)到\(n\)，而不是整个列表呢？这里也是为了消除重复解，我们没必要再对在\(i\)之前的元素进行分析了，这是因为通过前面元素所组成的解必会在固定位置为它时被找到。那么下面就是如何使用双指针算法了。

我们令左指针\(L=i+1\)，右指针\(R=n-1\)，当\(L时，执行循环：

当\(nums[i]+nums[L]+nums[R]==0\)，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将\(L,R\)移到下一位置，寻找新的解。若和大于\(0\)，说明\(nums[R]\)太大，$R $左移；若和小于\(0\)，说明\(nums[L]\)太小，\(L\)右移。

这里还有个坑，是我未AC后根据所给示例发现的，所给的示例为[-2 0 0 2 2]，这是算法中必须判断左界和右界是否和下一位置重复，去除重复解的由来