NC54 三数之和

题目链接：https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711

题目描述

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

数据范围：0≤n≤3000，数组中各个元素值满足 |val|≤100

空间复杂度：O(n^2)，时间复杂度 O(n^2)

注意：

• 三元组（a、b、c）中的元素可以按任意顺序排列。

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

示例 1：

输入：[-10,0,10,20,-10,-40]
返回值：[[-10,-10,20],[-10,0,10]]

示例 2：

输入：[-2,0,1,1,2]
返回值：[[-2,0,2],[-2,1,1]]

示例 3：

输入：[0,0]
返回值：[]

解题代码

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int len = num.length;
        if (len < 3 || num == null) {
            return res;
        }
        //对数组排序，从而保证不重复
        Arrays.sort(num);
        //排序后最小元素大于0
        if (num[0] > 0) {
            return res;
        }
        for (int i = 0; i < len - 2; i++) {
            //i去重
            if (i > 0 && num[i] == num[i - 1]) continue;
            //双指针
            int j = i + 1, k = len - 1;
            while (j < k) {
                if (num[i] + num[j] + num[k] == 0) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[k]);
                    res.add(temp);
                    //去重且更新j
                    int next = num[j];
                    while (num[j] == next && j < k) {
                        j++;
                    }
                } else if (num[i] + num[j] + num[k] < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }
}