牛客题解-NC54数组中相加和为0三元组

发表于 更新于 分类于 阅读次数：

题目

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

注意：

  1. 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）

  2. 解集中不能包含重复的三元组。

    1
    例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)

输入：

1
[-2,0,1,1,2]

返回值：

1
[[-2,0,2],[-2,1,1]]

思路

分析

通过Arrays.sort()方法对原数组进行排序，对于排序后的数据，从第一个元素开始，运用双指针（首尾双指针），求解该双指针指向数字之和为当前索引所在数字的相反数即可。实际上就转换成了多次的双指针求和问题。

需要特别注意的是在每一次指针移动过程中要判断是否有重复元素，重复元素需要跳过。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(num == null ||num.length < 3) return res;
        Arrays.sort(num);
        for(int i = 0; i<num.length-2; i++){
            if(num[i]>0){
                break;
            }
            if(i>0 && num[i]==num[i-1]){
                continue;
            }
            int l = i + 1, r = num.length - 1;
            while(l<r){
                int sum = num[i] + num[l] + num[r];
                if(sum == 0){
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(num[i]);
                    tmp.add(num[l]);
                    tmp.add(num[r]);
                    res.add(tmp);
                    while(l<r && num[l] == num[l+1]){
                        l++;
                    }
                    while(l<r && num[r] == num[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }else if(sum > 0){
                    r--;
                }else if(sum < 0){
                    l++;
                }
            }
        }
        return res;
    }
}