题目描述

给出一个有n个元素的数组S，S中是否有元素a,b,c 满足 a+b+c=0? 找出数组S中所有满足条件的三元组。

数据范围：0<= n <= 1000 ，数组中各个元素满足 |val|<= 100
注意：三元组(a,b,c)中的元素必须按非降序排列。解集中不能包含重复的三元组。

例：
S= {-10 0 10 20 -10 -40}，
解集为(-10, -10, 20), (-10, 0, 10)

题目分析

获取三元组的思路可以借鉴二元组（两个数之和为0），区别是需要先确定一个数，然后找和等于它的相反数的另两个数，其实就是多了一层循环，不断更改确定的数，主要思路代码如下：

for(int i=0;i<nums.length;i++){
	int target = -nums[i];
    // 在后面的数中找和等于目标值的两个数
    for(int j=i+1;j<nums.length;j++){
    	if(存在两个数的和 == target){
        	//将三个数都加入结果中
        }
    }
}

解题思路

方法1：使用双指针，先确定一个数，找到和等于它的相反数的两个数

1.在找寻和为目标数的过程中，需要将相同的数字跳过，避免结果的重复。
2.双指针的特点是在数组有序时，一个指向数组头部（最小的数），一个指向数组尾部（最大的数），这样在判断和的大小时，才能确定指针的移向。

alt

方法2：dfs递归遍历三元组，记录和为0的三元组

1.对于数组中k个数字的组合问题，都可以使用dfs递归的方法来解决，其根本就是遍历n个数字中挑选k个数字，将满足条件的组合加入到结果中，不满足的返回。
2.因为也需要对结果进行去重，所以需要添加一个判断条件跳过重复的部分。
3.为了减少时间消耗，可以对一些明显不符合条件的情况进行剪枝。

代码实现

方法1：双指针

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // 排序数组
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 若数组最小的数都大于0，或者最大的数都小于，则不存在三元组
        if(num.length == 0 || num[0] > 0 || num[num.length-1] < 0){
            return res;
        }
        for (int i = 0; i < num.length - 2; ++i) {
            // 设置目标数为 -num[i]，在从i+1 到数组末尾选择和等于目标数的两个数
            int j = i + 1;
            int k = num.length - 1;
            int target = -num[i];
            // 进行判断
            while (j < k) {
                // 如果和大于target，需要减小最大数（往左移）
                if (num[j] + num[k] > target) --k;
                // 如果和小于target，需要增加最小数（往右移）
                else if (num[j] + num[k] < target) ++j;
                else {
                    // 和刚好等于target，则记录结果
                    ArrayList<Integer> current = new ArrayList<>();
                    current.add(num[i]);current.add(num[j]);current.add(num[k]);
                    res.add(current);
                    // 将相同的数跳过
                    while (j + 1 < k && num[j+1] == num[j]) ++j;  // 防止重复
                    while (k - 1 > j && num[k-1] == num[k]) --k;  // 防止重复
                    ++j; --k;
                }
            }
            while (i + 1 < num.length - 2 && num[i+1] == num[i]) ++i;   // 防止重复
        }
        return res;
    }
}

时间复杂度： $O (n^{2})$ ，双指针外层循环n-2次，对前n-2个数又需要进行时间级别为n的数字查找（每次只移动一个下标），所以总体时间复杂度为 $O (n^{2})$ ；

空间复杂度： $O (1)$ ，只需要使用常数级别的变量。

方法2：dfs递归遍历

import java.util.*;
public class Solution {
    // 保存最终结果
    ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        res = new ArrayList<>();
        // 对数组进行排序
        Arrays.sort(num);
        // 使用递归遍历三元组的情况
        dfs(num, 0, 0, new ArrayList<Integer>());
        return res;
    }
    
    public void dfs(int[] num, int start, int sum, ArrayList<Integer> nums){
        // 访问玩数组返回
        if(start > num.length) return;
        // 当访问最后一个数且和大于0 或者不是最后一个但和与后一个数都大于0 可以直接返回
        if(sum > 0 && ((start <num.length && num[start]>0) || (start == num.length))) return;
        // 当和等于3且刚好是三个数，记录结果
        if(sum == 0 && nums.size() == 3){
            res.add(new ArrayList<Integer>(nums));
            return;
        }
        // 其他情况直接返回
        if(nums.size() >= 3) return;
        // 遍历所有的可能的数
        for(int i=start;i<num.length;i++){
            if(i > start && num[i] == num[i-1]) continue;
            // 选择num[i]
            nums.add(num[i]);
            dfs(num, i+1, sum+num[i], nums);
            // 撤销选择
            nums.remove(nums.size()-1);
        }
    }
}

时间复杂度： $O (n^{3})$ ，n个数字中三个数字的组合数为 $C_{n}^{3}$ ，实际上可以通过剪枝排除一些情况减少一些时间，总体时间消耗为 $O (n^{3})$ ；

空间复杂度： $O (1)$ ，因为记录数字的列表nums最多存3个数，dfs递归深度最多为3，在递归方法中也只需使用常数级别的变量，所以时间复杂度为 $O (1)$ 。

题解 | NC54 #数组中相加和为0的三元组#

题目描述

题目分析

解题思路

代码实现