前言
多少人梦想开始的地方，两数之和。
但是今天要聊的不是入门第一题，也没有面试官会考这一题吧…不会真有吧？
咳咳不管有没有，今天的猪脚是它的兄弟，三数之和，作为双指针经典题目之一，也是常常作为面试常考题出现。今天就来和大家分析分析这题的详细解法和双指针题目的思路。
三数之和
题目链接：15. 三数之和
示例 1：
输入： nums = [-1,0,1,2,-1,-4]
输出： [[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
初始代码：
var threeSum = function(nums) {
};
解题思路
看完了题目，这题的重点是：
- 数组是无序的
- 不能有重复的答案
- 每个答案数组都需要进行记录，同时i!=j,j!=k，
那么先开始思考：
- 暴力是否可以得出答案，答案是可以的。好下课- ̗̀(๑ᵔ⌔ᵔ๑)！，咳咳但是由于暴力时间复杂度为O(n)^3所以铁定是超时的
- 那么接下就是是否能进行优化，暴力是会具有大量的重复查询，我们需要做的是消除重复查询并且缩短查询时间
- 消除重复查询的办法，我选择的是对数组先进行排序。这样相同的元素放在一起，可以防止重复查询。
- 缩短查询时间，我选择的是双指针，既然是双指针，那么必须需要固定好一个数，才能让双指针进行移动。这里我选择的是固定第一个数字，第二个数字为左指针指向第一个数字后的一位数，第三个数字为右指针指向数组末尾的数。下面是例图：
因为数组是已经排好了序，所以我们只需要把这题当作一下问题求解即可：
当给你一个数target，让你在一个有序数组中找到两个数和为(-target)的所有解,并且解不能相同。是不是感觉特别简单。从三个数的寻找直接变成了两个数求和 ，那么接下来就来开始做题。
做题步骤
下面是伪代码，大家可以看着能不能写出来♡⸜(˶˃ ᵕ ˂˶)⸝♡
var threeSum = function(nums) {
//1- 首先定义一个返回的结果数组，result
//2- 对数组进行排序
//3- 排好序之和就进行数组遍历
//数组遍历从下标0开始，先遍历第一个数的范围（arr.length-3）,因为三数之和必须需要三个数
// 所以第一个数的下标范围为 0-length-3
//4- 第一个数被固定后，需要进行双指针遍历剩余的数，但是在遍历之前我们需要进行去除
//重复元素的操作，就是判断第一个数为target时候是否已经查询过结果，如果查询过就直接跳过
//5-去重之后，就定义双指针一个指向第一个数之后，一个指向数组末尾,定义一个数记录三数之和，方便我
//们移动双指针
//6-我们这里需要循环判断，压缩数组的空间，来找到所有符合的答案，所以这里我们需要while循环
//直到条件为左指针>=右指针下标时结束寻找
//7-如果答案符合我们需要进行记录，并且，第二个数和第三个数也需要进行去除重复元素的操作
//8- 结束循环返回result数组
};
正式代码：
var threeSum = function(nums) {
//1- 首先定义一个返回的结果数组，result
const result = [];
//2- 对数组进行排序
nums.sort((a,b)=>a-b);
//3- 排好序之和就进行数组遍历
//数组遍历从下标0开始，先遍历第一个数的范围（arr.length-3）,因为三数之和必须需要三个数
//所以第一个数的下标范围为 0-length-3
for(let i=0,len=nums.length;i<=len-3;i++){
//4- 第一个数被固定后，需要进行双指针遍历剩余的数，但是在遍历之前我们需要进行去除
//重复元素的操作，就是判断第一个数为target时候是否已经查询过结果，如果查询过就直接跳过,如果第一
//数大于0，那么也无需进行遍历直接返回即可因为数组是排好序的。第一个数都大于0，那么三数之和不可能为0
if(nums[i]>0)return result;
if(i!=0&&nums[i]==nums[i-1]){continue;}
//5-去重之后，就定义双指针一个指向第一个数之后，一个指向数组末尾,定义一个数记录三数之和，方便我
//们移动双指针
let sum =0;let left = i+1;let right = len-1;
//6-我们这里需要循环判断，压缩数组的空间，来找到所有符合的答案，所以这里我们需要while循环
//直到条件为左指针>=右指针下标时结束寻找
while(left<right){
sum =nums[i]+nums[left]+nums[right];
//7-如果答案符合我们需要进行记录，并且，第二个数和第三个数也需要进行去除重复元素的操作
if(sum==0){
result.push([nums[i],nums[left],nums[right]])
while(left<right&&nums[left]==nums[left+1]){
left++;
}
while(right>left&&nums[right]==nums[right-1]){
right--;
}
left++;right--;
}else if(sum>0){right--;}
else{
left++;
}
}
//8- 结束循环返回result数组
}
return result;
}
可以看到效率还是非常不错的，那么本题的分享到此结束。
谢谢大家的观看，喜欢的话可以点个关注或者是点赞，谢谢- ̗̀(๑ᵔ⌔ᵔ๑)。
