三数之和

小灰灰 2023-02-18 09:33 8阅读 0赞

## 一、前言 ##

问题来源LeetCode

问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1020/][https_leetcode-cn.com_explore_interview_card_bytedance_243_array-and-sorting_1020]

## 二、题目 ##

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

## 三、思路 ##

提供三种解决方法：

解决方法一：全排序前面三个，对满足条件的结果过进行去重。执行效率很低

解决方法二：排序 + 二分查找

先对数组进行排序，确定2个数字，对第三个二分查找。

时间复杂度：n\*n\*logn。

解决方法三：排序 + 首尾搜索

先对数组进行排序，确定一个数字，另外两个通过首尾搜索找到满足条件的。

时间复杂度：n\*n

## 四、总结 ##

先需要理解好题意，三个数不能重复，且和为0。

方法一，对前面三个数进行全排序对满足条件的结果进行去重，可以解决这个问题，但去重的成本太高了。

方法二，先进行了一次排序，通过两次循环可以确定2个数字，通过二分查找确定第三个数，排序后的数组可以保证结果集不会重复，相比方法一效率提升了很多。

方法三，先进行排序，通过循环确定第一数字，再首尾往中间搜索，来找后面两数字，效率相比前面两种方法效率更好。方法三，运用了排序后的数字的特点，要想在一个有序数组中找到2个和为一个固定数，那么一个数增加另一个数就必须减少，正好满足首尾向中间搜索的过程。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file    : 01_ThreeSum.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/106797084
    * @author  : niebingyu
    * @title   : 三数之和
    * @purpose : 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
    * 注意：答案中不可以包含重复的三元组。
    *
    * 示例 1:
    * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    *
    * 满足要求的三元组集合为：
    * [
    *   [-1, 0, 1],
    *   [-1, -1, 2]
    * ]
    *
    * 来源：力扣（LeetCode）
    * 链接：https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/
    * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    */
    //==========================================================================
    #pragma once
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_THREESUM namespace NAME_THREESUM {
    #define NAMESPACE_THREESUMEND }
    NAMESPACE_THREESUM
    
    // 累加数字个数
    #define NUMCOUNT 3
    
    // 方法一：全排序前面三个，对满足条件的结果过进行去重。
    // 效率很差
    class Solution_1 
    {
    public:
    	vector<vector<int>> threeSum(vector<int>& nums) 
    	{
            if (nums.size() < NUMCOUNT)
                return {};
            
            vector<vector<int>> res;
            threeSum(nums, 0, 0, res);
    		return res;
    	}
    
    private:
        void threeSum(vector<int>& nums, int count, int index, vector<vector<int>>& res)
        {
            if (count == NUMCOUNT)
            {
                int sum = 0;
                for (int i = 0; i < NUMCOUNT; ++i)
                    sum += nums[i];
    
                if (sum == 0)
                {
                    vector<int> t;
                    for (int i = 0; i < NUMCOUNT; ++i)
                        t.push_back(nums[i]);
    
                    sort(t.begin(), t.end());
                    // 排除重复
                    for (int i = 0; i < res.size(); ++i)
                    {
                        bool br = true;
                        for (int j = 0; j < NUMCOUNT; ++j)
                        {
                            if (res[i][j] != t[j])
                            {
                                br = false;
                                break;
                            }
                            
                        }
    
                        if (br)
                        {
                            return;
                        }
                    }
                    res.push_back(t);
                }
                return;
            }
    
            for (int i = count; i < nums.size(); ++i)
            {
                swap(nums[count], nums[i]);
                threeSum(nums, count+1, i, res);
                swap(nums[count], nums[i]);
            }
        }
    };
    
    // 方法二：排序 + 二分查找
    // 先对数组进行排序，确定2个数字，对第三个二分查找
    // 时间复杂度：n*n*logn
    class Solution_2
    {
    public:
        vector<vector<int>> threeSum(vector<int>& nums)
        {
            if (nums.size() < NUMCOUNT)
                return {};
    
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            for (int i = 0; i < nums.size()-2; ++i)
            {
                if (i > 0 && nums[i - 1] == nums[i])
                    continue;
    
                for (int j = i+1; j < nums.size() - 1; ++j)
                {
                    if (j > i+1 && nums[j-1] == nums[j])
                        continue;
                    
                    int ret = findNum(nums, j+1, nums.size() - 1, 0 - nums[i] - nums[j]);
                    if (ret >= j + 1 && ret <= nums.size() - 1)
                    {
                        vector<int> t = { nums[i], nums[j], nums[ret] };
                        res.push_back(t);
                    }
                }
            }
    
            return res;
        }
    
    private:
        int findNum(const vector<int>& nums, int left, int right, int num)
        {
            // b e,范围判断
            if (left < 0 || left >= nums.size() || right < 0 || right >= nums.size())
                return -1;
    
            
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == num)
                    return mid;
                else if (nums[mid] > num)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            
            return -1;
        }
    };
    
    // 方法三：排序 + 首尾搜索
    // 时间复杂度：n*n
    class Solution_3
    {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) 
        {
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans;
            int len = nums.size();
            for (int i = 0; i < len; ++i) 
            {
                if (i > 0 && nums[i] == nums[i - 1])
                    continue;
    
                int target = nums[i];
                if (target > 0) 
                    break;
                
                int l = i + 1, r = len - 1;
                while (l < r) 
                {
                    if (target + nums[l] + nums[r] < 0) 
                        ++l;
                    else if (target + nums[l] + nums[r] > 0) 
                        --r;
                    else 
                    {
                        ans.push_back({ target, nums[l], nums[r] });
                        ++l;
                        --r;
                        while (l < r && nums[l] == nums[l - 1])++l;
                        while (l < r && nums[r] == nums[r + 1])--r;
                    }
                }
            }
            return ans;
        }
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, vector<int> nums, int expect)
    {
    	Solution_2 S;
    	vector<vector<int>>  result = S.threeSum(nums);
    
    	// 粗略校验
    	if (result.size() == expect)
    		cout << testName << ", solution passed." << endl;
    	else
    		cout << testName << ", solution failed. result:" << result.size() << " ,expect:" << expect << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums =
        {
            1, 2, -3,
        };
    
        int expect = 1;
    
        test("Test1()", nums, expect);
    }
    
    void Test2()
    {
    	vector<int> nums = 
    	{
            -1, 0, 1, 2, -1, -4
    	};
    
    	int expect = 2;
    
    	test("Test2()", nums, expect);
    }
    
    NAMESPACE_THREESUMEND
    // 测试 用例 END
    //
    
    void ThreeSum_Test()
    {
        NAME_THREESUM::Test1();
    	NAME_THREESUM::Test2();
    }

[https_leetcode-cn.com_explore_interview_card_bytedance_243_array-and-sorting_1020]: https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1020/