LeetCode题解：三数之和

题目描述

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

示例

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

思路方法

我们其实可以将这道题转化为LeetCode两数之和那道题，具体做法如下：
前提条件，我们需要将数组排序。
首先，外层遍历，作为第一个数first，并且将目标数target设置为-nums[first]。
接下来，我们只需要两个双指针second与third，分别指向first+1与最后一个数，两个指针随着遍历向中靠拢。如果nums[second]+nums[third]>target，那么third就左移，否则，second就左移。而second是随着内层遍历而增加的。
因为我们事先将数组进行了排序，所以当内层循环达到second=third时依然找不到答案，那么就跳过内层循环，直接遍历下一个first。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      int n = nums.length;
      Arrays.sort(nums);
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      //枚举a
      for(int first=0;first<n;first++){
          //需要和上次枚举的数不同
          if(first>0&&nums[first]==nums[first-1]){
              continue;
          }
          //c对应的指针初始值对应数组的末端
          int third = n-1;
          int target = -nums[first];
          //枚举b
          for(int second=first+1;second<n;second++){
              //需要和上次枚举的数不同
              if(second>first+1&&nums[second]==nums[second-1]){
                  continue;
              }
              //需要保证b的指针在c的指针的左边
              while(second<third&&nums[second]+nums[third]>target){
                  third--;
              }
              //如果指针重合，随着后续的变化，就不会有满足a+b+c=0并且b<c的c了
              //可以退出循环
              if(second==third){
                  break;
              }
              if(nums[second]+nums[third]==target){
                  List<Integer> list = new ArrayList<Integer>();
                  list.add(nums[first]);
                  list.add(nums[second]);
                  list.add(nums[third]);
                  result.add(list);
              }
          }
      } 
      return result; 
    }
}

复杂度分析

• 时间复杂度：O(N^2)
• 空间复杂度：O(logN),我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)。