2021/4/7 三数之和

题目描述

描述转载自力扣《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

2. 因为题目要求不准出现重复的三元组，所以我们可以先将数组排个序，每次遍历时有
   
   
   
   这样就不会出现重复的三元组了。

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

3. 当我们固定 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;
    }
}