05-数据结构与算法
双指针法
左右指针

三数之和

# 📃 题目描述

题目链接：

给你一个包含 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. 两数之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 和 454. 四数相加 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)，总的思想都是固定一半，然后去找另一半。对于这道题目，找出一个数组中的三个数，我们同样可以固定 a 和 b，去找 c。具体来说，先将这个数组存入 map，然后利用两个 for 循环求出 a 和 b 之和，判断 0-(a+b) 也就是 c 是否在 map 里出现过即可（并且这个 0-(a+b) 还得在 b 的右边））。

具体的细节来说，由于需要避免重复元组，所以我们需要对数组进行一个排序，循环的过程中跳过重复元素。

class Solution {

    private final static Integer TARGET = 0;

    public List<List<Integer>> threeSum(int[] nums) {
        // 存储三元组
        List<List<Integer>> res = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return res;
        }

        // 对数组进行排序
        Arrays.sort(nums);

        // 将数组存入 map, 相等的值只会放进去一个, i 为下标
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i ++) {
            map.put(nums[i], i);
        }

        // 两层循环固定 a 和 b
        // 遍历获得 a
        for (int i = 0; i < nums.length; i ++) {
            // 若 nums[i] > 0，由于数组已经有序，所以它后面的一定也 > 0，直接返回，那么一定不可能找到第一个数为 nums[i] 且和为 0 的三元组了
            if (nums[i] > 0) {
                break;
            }

            // 对 a 进行去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 遍历获得 b
            for (int j = i + 1; j < nums.length; j ++) {
                // 对 b 进行去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int c = TARGET - nums[i] - nums[j];
                // 尝试从哈希表中获取第三个数字 c, 若存在，并且第三个数字需要在第二个数字右侧(防止重复)
                if (map.containsKey(c) && map.get(c) > j) {
                    res.add(Arrays.asList(nums[i], nums[j], c));
                }
            }
        }

        return res;
    }
}

需要注意的就是对 a 和 b 都要进行去重操作：

空间复杂度：O(N^2)（如果我们忽略掉用于存储答案的空间，那么该算法的空间复杂度主要来自于排序，额外的排序的空间复杂度为 O(logN)）
时间复杂度：排序的时间复杂度是 O(nlogn)，两层循环处理的时间复杂度是 O(N^2)，所以总时间复杂度为 O(N^2)

# 双指针

双指针法做这道题目会更简单。思路如下：

1）对数组进行排序

2）遍历排序后的数组

若 nums[i] > 0，由于数组已经有序，所以它后面的一定也 > 0，直接返回
对于重复元素，跳过
两个指针，左指针 left 指向 i + 1，另一个右指针 right 指向数组的最后一个元素：
- 若 nums[i] + nums[left] + nums[right] = 0，说明这三个就是符合要求的元组。然后 left ++，right -- 寻找新的解（需要注意的是，在移动的过程中，记得进行去重，跳过重复元素）
- 若 nums[i] + nums[left] + nums[right] < 0，left ++
- 若 nums[i] + nums[left] + nums[right] > 0，right --

单层 for 循环固定一个元素，然后用双指针法找剩下的两个元素（前提是数组有序）。

class Solution {

    private final static Integer TARGET = 0;

    public List<List<Integer>> threeSum(int[] nums) {
        // 存储三元组
        List<List<Integer>> res = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return res;
        }

        // 1. 对数组进行排序
        Arrays.sort(nums);

        // 2. 遍历处理数组
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] > 0) {
                break;
            }
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 左右指针
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 跳过重复元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left ++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right --;
                    }

                    // 开始寻找新的解
                    left ++;
                    right --;
                } else if (sum < 0) {
                    left ++;
                } else {
                    right --;
                }
            }
        }

        return res;
    }
}