Day 26 - 15. 3sum

Day26 - 15.三数之和

LeetCode 15.三数之和

题目链接：

https://leetcode.cn/problems/3sum/

1. 题目描述

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

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

举个例子：

输入： 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. 结果的去重策略。

例如：对于 a + b + c = 0

此时一层循环固定 a，此时问题变为 找出 b+ c == -a，就可以转化为双指针问题。

首先对数组nums进行升序排序，类似「167.两数之和II」，本次使用三个索引：i，left，right。初始值i = 0，left = i + 1，right = nums.size - 1。

算法如下：

1. nums[i] + nums[left] + nums[right] > target时，nums[left]或nums[right]需要一个更小的值，由于nums是升序的，故只能把索引right往左移，--right。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。

2. nums[i] + nums[left] + nums[right] < target时，nums[left]或nums[right]需要一个更大的值，由于nums是升序的，故只能把索引left往右移，++left。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。

3. nums[i] + nums[left] + nums[right] == target时，把当前三元组存到结果数组中，并且left右移直到nums[left-1] != nums [left](对nums[left]去重)去寻找下一个满足条件的三元组。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。

4. 如果i == nums.size()，算法结束。

3. C++代码

3.1. 暴力算法

老规矩，先上暴力！

暴力算法很容易想到，枚举三层变量...

关键是要处理好：

• 无重复三元组

• 边界条件

• 特殊情况（数组本来就不满三个...等等）

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> res;
        int nums_len = nums.size();
        // 如果数组的元素少于三个，直接返回空
        if (nums_len < 3)
        {
            return res;
        }
        // 先对数组进行排序，方便去重
        // 快速排序 复杂度O(nlogn)
        sort(nums.begin(), nums.end());
        // 注意循环条件，由于 j,k 存在，i 不能达到 nums_len - 2
        for (int i = 0; i < nums_len - 2; i++)
        {
            // 去除重复元素，如果重复，以最后一个为基准
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            // 注意循环条件，从i + 1开始，不能达到 nums_len - 1
            for (int j = i + 1; j < nums_len - 1; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }
                for (int k = j + 1; k < nums_len; k++)
                {
                    if (k > j + 1 && nums[k] == nums[k - 1])
                    {
                        continue;
                    }
                    // 此时判断找到的三元组是否符合条件
                    if ((nums[i] + nums[k] + nums[j]) == 0)
                    {
                        res.push_back({nums[i], nums[j], nums[k]});
                    }
                }
            }
        }
        return res;
    }
};

复杂度，可预见的超时...

3.2. 双指针算法

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> res;
        int nums_len = nums.size();
        // 正常排序方便去重
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums_len; i++)
        {
            int left = i + 1;
            int right = nums_len - 1;
            // 正常去重操作
            if (i > 0 && nums[i - 1] == nums[i])
            {
                continue;
            }
            // 双指针大循环
            while (left < right)
            {
                // 找到符合条件的三元组
                if (nums[i] + nums[left] + nums[right] == 0)
                {
                    // 添加进返回值
                    res.push_back({nums[i], nums[left], nums[right]});
                    // 左指针移动
                    left++;
                    // 左指针移动有可能出现重复值，所以也需要去重
                    // 注意去重条件
                    while (left < right && nums[left - 1] == nums[left])
                    {
                        left++;
                    }
                }
                // 小于 0，说明需要更大的值，根据之前排好序的数组，只能移动左指针
                // 并且此时不用去重，因为就算重复，也只会继续循环，不会影响返回值，无非是多做几次循环
                else if (nums[i] + nums[left] + nums[right] < 0)
                {
                    left++;
                }
                // 大于 0，说明需要移动右指针
                else if (nums[i] + nums[left] + nums[right] > 0)
                {
                    right--;
                }
            }
        }
        return res;
    }
};

复杂度虽然没有很出色：，但也够用。

关键是思路要打开，这个算法很好的把 三数之和 变为 两数之和，转化为双指针问题。

4. 复杂度分析

时间复杂度： 首先排序最快 O(nlogn)，然后索引i遍历一遍字符串nums，针对每个i，都有left和right共同遍历一遍nums，总共需要 O(n2)，故时间复杂度是 (nlogn) + O(n2) = O(n2)。

空间复杂度： 主要是排序消耗的空间，看具体的排序算法，快排的话是O(logn)，寻找三数之和的过程需要一个结果数组空间复杂度是O(n)，故总的空间复杂度是O(n)。

5. Redo. 02/04

双指针：左右指针收缩

预先排序：复杂度

去重操作：判断相邻元素是否相等

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> res;
        int nums_len = nums.size();
        sort(nums.begin(), nums.end());
        for(int a = 0; a < nums_len; a++)
        {
            if(a > 0 && nums[a] == nums[a - 1])
            {
                continue;
            }
            int left = a + 1;
            int right = nums_len - 1;
            while(left < right)
            {
                if(nums[a] + nums[left] + nums[right] == 0)
                {
                    res.push_back({nums[a], nums[left], nums[right]});
                    left++;
                    while(left < right && nums[left - 1] == nums[left])
                    {
                        left++;
                    }
                }
                else if(nums[a] + nums[left] + nums[right] < 0)
                {
                    left++;
                }
                else if(nums[a] + nums[left] + nums[right] > 0)
                {
                    right--;
                }
            }
        }
        return res;
    }
};