[HOT 100] 0015. 三数之和

1. 题目链接

15. 三数之和 - 力扣（LeetCode）

2. 题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

3. 题目示例

示例 1 :

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2 :

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3 :

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

4. 解题思路

思路: 先排序 + 双指针

1. 排序：

• 首先对输入数组进行排序，以便能够使用双指针法有效查找三元组。
• 排序后的数组有助于避免重复的三元组，因为可以跳过重复的元素。

2. 枚举第一个数：

• 我们将数组中的每个元素作为第一个数 nums[first]，然后使用双指针来寻找与其相加为 0 的另外两个数。

3. 双指针法：

• 对于固定的 first，我们可以用两个指针 second 和 third 来查找 nums[second] 和 nums[third]，使得 nums[first] + nums[second] + nums[third] = 0。
  • second 从 first + 1 开始，third 从数组的末尾开始。
  • 如果当前三数之和大于零，则移动 third 向左（减少和）。
  • 如果当前三数之和小于零，则移动 second 向右（增大和）。
  • 如果三数之和为零，记录该三元组，并且避免重复，继续移动指针。

4. 跳过重复的元素：

• 为了避免重复的三元组，我们在枚举 first 和 second 时，跳过和上一个元素相同的值。
• first > 0 && nums[first] == nums[first - 1]：如果当前 first 的值和前一个 first 的值相同，则跳过。
• second > first + 1 && nums[second] == nums[second - 1]：如果当前 second 的值和前一个 second 的值相同，则跳过。

5. 返回结果：

• 经过两层循环和双指针操作，最终返回所有符合条件的三元组。

5. 题解代码

Java 代码 :

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;

        // 排序
        Arrays.sort(nums);

        // 枚举 A
        for(int first = 0; first < n; first++){
            // 与上次枚举的数不相同
            if(first > 0 && nums[first] == nums[first-1]) continue;

            // C的指针指向数组的末端
            int third = n-1;
            int target = -nums[first];

            // 枚举 B
            for(int second = first + 1; second < n; second++){
                // 与上次枚举的数不相同
                if(second > first + 1 && nums[second] == nums[second-1]) continue;

                // 保证 B 的指针在 C 的左侧
                while(second < third && nums[second] + nums[third] > target) third--;

                // 如果 B/C 指针重叠, 则B向后移
                if(second == third) break;

                if(nums[second] + nums[third] == target){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[first]);
                    temp.add(nums[second]);
                    temp.add(nums[third]);
                    res.add(temp);
                }
            }
        }
        return res;
    }
}

6. 复杂度分析

• 时间复杂度: 外层循环枚举第一个数 first，内层循环枚举第二个数 second，并用双指针查找第三个数。每次操作的时间复杂度是 O(n)，所以总体时间复杂度是 O(n^2)。
• 空间复杂度: 我们使用了一个结果列表 res 来存储三元组，最坏情况下会存储 O(n^2) 个三元组。
• 排序数组时需要 O(log n) 的空间来存储排序过程中的临时数据。 所以，空间复杂度是 O(n)。