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

示例 1：

  1. 输入：nums = [-1,0,1,2,-1,-4]
  2. 输出：[[-1,-1,2],[-1,0,1]]

示例 2：

  1. 输入：nums = []
  2. 输出：[]

示例 3：

  1. 输入：nums = [0]
  2. 输出：[]

提示：

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

排序 + 双指针

本题的难点在于如何去除重复解。

算法流程：

  1. 特判，对于数组长度 n，如果数组为 null或者数组长度小于 33，返回 []。
  2. 对数组进行排序。
  3. 遍历排序后数组：
  • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
  • 对于重复元素：跳过，避免出现重复解
  • 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
    1. 1. 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
    2. 2. 若和大于 0，说明 nums[R]太大，R 左移
    3. 3. 若和小于 0，说明 nums[L] 太小，L 右移
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var threeSum = function(nums) {
  6.     const n = nums.length;
  7.     let res = [];
  8.     nums.sort((a, b) => a - b)
  9.     if(nums.length < 3) {
  10.         return [];
  11.     }
  12.     for(let i = 0; i < nums.length; i++ ) {
  13.         if(nums[i] > 0){
  14.             return res;
  15.         }
  16.         // 去重
  17.         if(i > 0 && nums[i] === nums[i-1]) {
  18.             continue
  19.         }
  20.         let L = i+1;
  21.         let R = n-1;
  22.         while(L < R) {
  23.             const sum = nums[i] + nums[L] + nums[R];
  24.             if(sum === 0){
  25.                 res.push([nums[i], nums[L], nums[R]]);
  26.                 // 去重
  27.                 while(L<R && nums[L] === nums[L+1]) {
  28.                     L++
  29.                 }
  30.                 // 去重
  31.                 while(L<R && nums[R] === nums[R-1]) {
  32.                     R--
  33.                 }
  34.                 R--;
  35.                 L++;
  36.             } else if(sum > 0){
  37.                 R--
  38.             } else{
  39.                 L++
  40.             }
  41.         }
  42.     }
  43.     return res
  44. };

作者：wu_yan_zu
链接：https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。