LeetCode15.三数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode15.三数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

15.三数之和

一、题目

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

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

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

示例 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 。

提示：

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

二、解法

方法一：哈希法（非常烧脑的办法，我自己一开始没想出来）

直接给出代码，我感觉最难想的就是注释部分，有兴趣的话可以用{-2,-2,-2,-1,-1,-1,0,0,0,1,1,1,2,2,2}这个案例自己推一推，就能理解代码里为什么这么做了。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++){
            if (nums[i] > 0) {
                break;
            }
            //当元素a前一个元素已经被处理过的时候，就跳过
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            unordered_set<int> s;   
            for(int j = i + 1; j < nums.size(); j++){
                //当元素b和前两位相等，且前两位都不是a的情况下，可以跳过
                if(j>i+2 && nums[j-1]==nums[j] && nums[j-2]==nums[j-1]){
                    continue;
                }
                int c = 0-nums[i]-nums[j];
                if(s.find(c) != s.end()){
                    result.push_back({nums[i],nums[j],c});
                    s.erase(c); //如果减出来的元素曾经存在于s中,就消除s里所有等于c的元素
                }else{
                    s.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

方法二：双指针（推荐）

算法思路：

给定一个整数数组 nums，我们需要找到所有满足以下条件的三元组 [nums[i], nums[j], nums[k]]：

i != j，i != k，j != k；
nums[i] + nums[j] + nums[k] == 0。

我们可以使用双指针的方法。

首先，对数组进行排序，这样可以方便后续的指针移动操作。然后，我们遍历排序后的数组，将当前元素作为三元组的第一个元素。使用两个指针，一个指向当前元素的下一个位置，另一个指向数组的最后一个位置。

在指针移动的过程中，我们计算当前三个元素的和 sum = nums[i] + nums[left] + nums[right]：

如果 sum 等于零，说明找到了一个满足条件的三元组，将这个三元组添加到结果列表中。
如果 sum 小于零，说明当前和偏小，我们需要增加和的值，因此将左指针向右移动一位。
如果 sum 大于零，说明当前和偏大，我们需要减小和的值，因此将右指针向左移动一位。

内部去重操作：在移动指针时，我们需要跳过重复的元素，以避免生成重复的三元组。如果当前指针所指的元素与前一个元素相同，我们可以继续移动指针，直到找到一个不同的元素为止。

详细实现：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 对数组进行排序
        vector<vector<int>> result;  // 存储结果的二维数组

        for (int i = 0; i < nums.size() - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;  // 外层循环去重操作

            int left = i + 1;  // 左指针
            int right = nums.size() - 1;  // 右指针

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {  // 找到满足条件的三元组
                    result.push_back({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 result;
    }
};