兄弟们，小菜鸟又来水算法了！好久没有写算法，今天要分享的是Leetcode里面的第15题——三数之和，听说这道题是梦破碎的地方。说实话，我是很讨厌写算法的，这些算法想的我脑阔子大，没办法谁让咱要吃这碗饭呢！哎，不说了，还是好好刷刷算法吧！这道题目的主要的算法思想是双指针哦！

手刃算法第五式：三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。 请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

题目分析

刚看到这道题的时候，我想着是利用双指针和hash表来做会不会简单点，只用看hash表中是否包含另外两个数的和的相反数。后来我仔细想了想，这样做好像也不简单。主要是去重不知道怎么去。难搞！

后来我想还是想老老实实的慢慢来搞吧，还没学会走呢就想着跑了。

按照简单的双指针思想，首先将数组进行排序，设置个起始点 i ，然后将 i 的后面一个位置设个指针为left，数组尾部设置个指针right，如图：

将这三个数加起来比较大小，如果比0大则说明最后一个数大了则需要将右指针往左移；如果比0小的话，则说明左指针小了，则需要将左指针往右移；如果正好等于0的话，那就将这个三个数作为数组存入一个新的数组中，同时移动两个指针。当两个指针相遇时则说明已经找完了，更换标准点在进行找一遍。

具体的代码实现

通过上面的思路我们可以编写出大致的代码：

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let result = []
    let len = nums.length

    for (let i=0;i<len;i++) {
        let left=i+1,right=len-1
        if(nums[i]>0||nums[right]<0||len<3){break}
        while(left < right){
           if(nums[i]+nums[right]+nums[left]>0){right--}
           else if(nums[i]+nums[right]+nums[left]<0){left++}
           else{
              result.push([nums[i],nums[right],nums[left]])
              while (left < right && nums[left] === nums[left + 1]) 
                  left++;
              while (left < right && nums[right] === nums[right - 1]) 
                  right--;
              eft++; right--
           }
        }
    }
    return result
};

将nums=[-1,0,1,2,-1, -4]作为形参运行一下得到这样的结果：

嗯哼？题目说了不能重复哦，这不是已经跳过了重复值嘛，怎么还有重复的啊？

仔细看一下代码的执行过程，哦~，虽然调过来左右的重复值，但是没有跳过起始的重复值，这还是没有啥用啊。

所以我们还应该加一个判断起始值是否重复的语句，如下：

if (i > 0 && nums[i] === nums[i - 1]) continue;

这个应该放在循环开始。这样就可以得到正确的结果了。

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let result = []
    let len = nums.length

    for (let i=0;i<len;i++) {
        let left=i+1,right=len-1
        if(i > 0 && nums[i] === nums[i - 1]){continue}
        if(nums[i]>0||nums[right]<0||len<3){break}
        while(left < right)
        if(nums[i]+nums[right]+nums[left]>0){right--}
        else if(nums[i]+nums[right]+nums[left]<0){left++}
        else{
           result.push([nums[i],nums[right],nums[left]]) 
           while (left < right && nums[left] === nums[left + 1]) 
            left++;
           while (left < right && nums[right] === nums[right - 1]) 
            right--;
           left++; right--
        }
        
    }
    return result
};

放到Leetcode里面检测一下：也是可行的。

大佬的解法

我看了一下力扣里面的题解，几个大佬里面的思想基本上就是这样，但是做了一些优化。大家感兴趣的可以去看看大佬的解答，15. 三数之和 - 力扣（LeetCode）。我在这里就不做过多的介绍，不然有点嫌疑！

小结

完成这道算法还是比较艰难地，对我来说。因为我这人老是忘记点啥东西，说实话，在写这道题目时用的return，break，continue这三个的做优都给搞混淆了，所以搞出了几次都是返回空数组。最后一看，原来是return用错了，应该用break的。现在记住了！真的记住了！！这道题目现在看来并不是很复杂，就是这个去重这方面还是有点难理解的。