题目描述

描述转载自力扣《15. 三数之和》
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例1

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

示例2

输入:nums = []
输出:[]

示例3

输入:nums = [0]
输出:[]

解题思路

  1. 如果本题允许出现重复的三元组,那就只需要三重循环暴力算法就能够得出答案了。下面是伪代码。
for i = 1..(len - 2)
    for j = (i + 1)..(len - 1)
        for k = (j + 1)..len
  1. 因为题目要求不准出现重复的三元组,所以我们可以先将数组排个序,每次遍历时有
    图片说明
    图片说明
    图片说明
    这样就不会出现重复的三元组了。
for i = 0..(len - 2)
    if (i > 0 && num[i] == num[i-1]) 
        continue
    for j = (i + 1)..(len - 1)
        if (j > i + 1 && num[j] == num[j-1]) 
            continue
        for k = (j + 1)..len
            if (k > j - 1 && num[k] == num[k-1]) 
                continue
  1. 当我们固定 i 的值时,有 图片说明 ,当 j 越大, k 就会越小,所以我们可以将 k 从后往前遍历,当 j 往后遍历时, k 就往前遍历。
for i = 0..(len - 2)
    if (i > 0 && num[i] == num[i-1])
        continue
    k = 0
    for j = (i + 1)..(len - 1)
        if (j > i + 1 && num[j] == num[j-1])
            continue
        while (j < k && num[i] + num[j] + num[k] > 0)
            --k
        if(num[i] + num[j] + num[k] == 0)
            记录三元组

Java 代码实现

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < num.length - 2; ++i) {
            if (i != 0 && num[i - 1] == num[i]) continue;
            int k = num.length - 1;
            for (int j = i + 1; j < num.length - 1; ++j) {
                if (j != i + 1 && num[j] == num[j - 1]) continue;
                while (j < k && num[i] + num[j] + num[k] > 0) --k;
                if (j == k) break;
                if (num[i] + num[j] + num[k] == 0) {
                    ArrayList<Integer> ele = new ArrayList<>();
                    ele.add(num[i]);
                    ele.add(num[j]);
                    ele.add(num[k]);
                    list.add(ele);
                }
            }
        }
        return list;
    }
}