题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 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

    解题思路

    a + b + c = 0
    也就是b + c = -a
    这实际是 排序数组中两个数字之和 的变体
    那么前提条件就是数组有序，因此先排序。
    随后以target = -a；
    双指针寻找可能的组合。

    实现代码

    1. public List<List<Integer>> threeSum(int[] nums) {
    2. List<List<Integer>> result = new ArrayList<>();
    3. if(nums.length<3){
    4.   return result;
    5. }
    6. // 排序
    7. Arrays.sort(nums);
    8. //  System.out.println(Arrays.toString(nums));
    9. // 双指针
    10. for (int i = 0; i < nums.length-2; i++) {
    11.   // 当前元素与上一个元素相同或者当前元素大于0就不用找了
    12.   if((i>0&&nums[i] == nums[i-1])||nums[i]>0){
    13.     continue;
    14.   }
    15.   // 从第一个元素开始起，寻找后面所有元素和为target的值
    16.   int target = -nums[i];
    17.   int minIndex = i+1;
    18.   int j = nums.length -1;
    19.   while(minIndex < j){
    20.     if(nums[minIndex] + nums[j] > target){
    21.       j--;
    22.     }
    23.     else if(nums[minIndex] + nums[j] < target){
    24.       minIndex++;
    25.     }
    26.     else {
    27.       if(!result.isEmpty()){
    28.         if(!(nums[i] == result.get(result.size()-1).get(0) && nums[minIndex] == result.get(result.size()-1).get(1))){
    29.           result.add(Arrays.asList(nums[i],nums[minIndex], nums[j]));
    30.         }
    31.       }else {
    32.         result.add(Arrays.asList(nums[i],nums[minIndex], nums[j]));
    33.       }
    34.       minIndex++;
    35.     }
    36.   }
    37. }
    38. return result;
    39. }

    时间及空间复杂度分析

时间复杂度是O(n2)，排序在这个过程中不是主要时间
image.png
值得注意的是，在这儿的List的方法比较耗时，如List.contains()，用于避重容易导致超时。

拓展思路