15.三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

示例 3：

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

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

解题

总体思路是参考1.两数之和，三数之和的话，只需选定一个数假定为A，那么就转化为两数之和问题了，要求解的另外两个数假定为B和C，满足B+C=-A，即两数之和问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret; // 保存结果三元组
        int len = nums.size();
        sort(nums.begin(), nums.end());
        if (nums[0] > 0 || nums[len-1] < 0) {
            return ret; // 过滤一下不可能凑出三数之和条件的情况
        }
        for (int i = 0; i < len; ++i) { // nums[i]即为选定的第一个数，那么剩下满足条件的两个数就是两数之和问题
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
            }
            int li = i + 1, ri = len - 1; // 定义双指针，左指针从左往右，右指针从右往左
            int target = -nums[i]; // nums[i]是选定的数，那么剩下两数之和则为-nums[i]
            while (li < ri) { // 左指针必须在右指针左边
                while (nums[li] + nums[ri] < target && li < ri) ++li; // 如果此时左右指针指向的两数之和比目标和小，说明应该增大其中某个数，即左指针右移
                if (li >= ri) break; // 当左右指针相遇了，说明不存在满足两数之和为target的两个数
                while (nums[li] + nums[ri] > target && li < ri) --ri; // 如果此时左右指针指向的两数之和比目标和大，说明应该减小其中某个数，即右指针左移
                if (li >= ri) break; // 当左右指针相遇了，说明不存在满足两数之和为target的两个数
                if (nums[li] + nums[ri] == target) { // 当找到两个数满足两数之和条件时
                    ret.push_back({nums[i], nums[li], nums[ri]}); // 与第一选定数合并即为满足三数之和的三元组，加入结果集合中
                    while (nums[li++] == nums[li] && li < ri); // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
                    if (li >= ri) break; // 当左右指针相遇了，说明所有可能的二元组都遍历完了
                    while (nums[ri--] == nums[ri] && li < ri); // 如果和上一轮循环判断的数相同则没必要再判断一次了，跳过直到遇到不同的数
                    if (li >= ri) break; // 当左右指针相遇了，说明所有可能的二元组都遍历完了
                }
            }
        }
        
        return ret;
    }
};