leetcode刷题：三数之和

题目：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 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] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

解题思路：

暴力法搜索时间复杂度为 O( $N^3$ )，可通过双指针动态消去无效解来优化效率。

算法流程：

先将 nums 排序，时间复杂度为 O( $Nl o g N$ )。
固定 3 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 ( $k, l e n (n u m s)$ )两端。
双指针 i, j 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i，j 组合：
- 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了。
- 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
- i，j 分设在数组索引 ( $k, l e n (n u m s)$ ) 两端，当i < j 时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
  - 当s < 0时，i += 1并跳过所有重复的nums[i]；
  - 当s > 0时，j -= 1并跳过所有重复的nums[j]；
  - 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。

代码：

class Solution {
   public List<List<Integer>> threeSum(int[] nums) {
       //数组从小到大排序
       Arrays.sort(nums);
       int len = nums.length;

       List<List<Integer>> res = new ArrayList<>();

       for(int i = 0; i < len -2; i++){
           //如果最小的数大于0则不可能三个数的和为0, 直接退出
           if(nums[i] > 0){
               break;
           }

           //如果和上一个数相同，则有重复解。
           //即当a = d时，a + b + c = d + b + c = 0, 寻找下一个不同的数（简称：去重）
           if(i > 0 && nums[i] == nums[i-1]){    //i > 0是因为可能i = 0时去重出现异常
               continue;
           }

           //取另外两个数，判断三数之和是否为0
           int j = i + 1, k = len - 1;
           int sum;


           while(j < k){
               sum = nums[i] + nums[j] + nums[k];

               //如果三数之和大于0，则说明最大数nums[k]太大了，k向左移，同时去重
               if(sum > 0){
                   while(j < k && nums[k] == nums[--k]);
               //如果三数之和小于0，则说明中间数nums[j]太小了，j向右移，同时去重
               }else if(sum < 0){
                   while(j < k && nums[j] == nums[++j]);
               //如果三数之和等于0, 则把三数添加到答案
               }else{
                   res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));

                   //nums[j]增大, nums[k]减小, 依旧可能满足三数之和为0，继续遍历去重
                   while(j < k && nums[k] == nums[--k]);
                   while(j < k && nums[j] == nums[++j]);
               }
           }

       }
       return res;
   }
}