LeetCode 15. 三数之和

原题链接： 15. 三数之和 - 力扣（LeetCode）

1. 理解题意

题意：给一个数组 nums，找出一个三元组，且这三个数字的下标两两互不相同，并且这三个数字相加之和为0，返回能够满足条件的且不重复的三元组。

这里的不重复，可以说是这道题最麻烦的一点，什么叫重复，比如： [0，-1，1] 和 [-1，0，1] 就是重复的。

2. 解决问题的思路

做这种问题，我们首先大概率想到的就是暴力枚举，因为它无脑，简单。

2.1. 暴力枚举

枚举出所有的三元组，接下来的操作就是去重，去重，也很简单，我们可以通过 set 去重，写一段伪代码，进攻参考：

for (size_t i = 0; i < n; ++i)
{
	for (size_t j = i + 1; j < n; ++j)
	{
		for (size_t k = j + 1; k < n; ++k)
		{
			if (IsVaild(nums[i], nums[j], nums[k]))
				myset.insert({ nums[i], nums[j], nums[k] });
		}
	}
}

上面枚举的时间复杂度为 O(N^3)， 如果提交，是会超时的。

2.2. 双指针 + 单调性

要使用双指针 + 单调性解决问题，首先需要数据有序，这是前提。

三数之和，我们其实可以看成一个二树之和，为什么呢？

比如 a + b + c == 0， 这是一个三数之和；我们也可以看成  (a + b) == -c，而这就是一个两数之和，两数之和，我们解决过。

因此，三数之和这个问题，我们可以按照如下思路解决：
在有序数组中，先固定一个值，这个值就是上面的 c；

然后，在剩下的区间中，采用两数之和的方案 (双指针 + 单调性)，找到 a + b == -c 的情况，此时的 a、b、c 就是一个满足题目要求的三元组。

接下来就是去重的操作了。

关于去重，如果在刷题，可以采用 set 去重，但如果是面试，建议不要用set，我们想想，什么情况会出现重复的三元组呢？

我们通过实例来理解，比如 nums = [-2，0，0，0，1，1，2，2]，如下：

此时 c  = -2， a = 0， b = 2， a + b + c 正好等于 0，因此，这就是一个合适的三元组，接下来，a 向右移动，b向左移动，因为此时 c 是固定的，a 向右移还是0，如果此时能构成合适的三元组，那么 b 一定是 2，换言之，此时 a = 0 就没有在判断的必要了，即 a = 0 能不能构成三元组都没有意义，因为就算能构成，也是重复的，故，此时 a 应该跳过0，同理， b 应该跳过 2，如下所示：

上面就是去重的逻辑，可是针对这一道题光有去重不够，我们还需要不漏，不漏指的是，在找到一个合适的三元组后，继续判断，直到 a 和 b 相遇，相遇后， c 向右移动，重复上述过程。

2.3. 代码编写 

理解了上面，代码如下：

class Solution {
public:
    inline int Compare(int x, int y, int target)
    {
        return x + y - target;
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        // 排序
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> ret;
        
        // 固定值, 相当于上图中的 c 的下标
        int objpos = 0;

        while(objpos <= nums.size() - 3)
        {
            // 最小值都大于0了, 后序就没必要在判断了, 一定没有合适的三元组
            if(nums[objpos] > 0)  break;

            int target = nums[objpos] * -1;
            // left 相当于 a 的下标
            int left = objpos + 1;
            // right 相当于 b 的下标
            int right = nums.size() - 1;

            // 这个逻辑就是两数之和的逻辑
            while(left < right)
            {
                int mid_ret = Compare(nums[left], nums[right], target);
                if(mid_ret > 0) right--;
                else if(mid_ret < 0) left++;
                else
                {
                    ret.push_back({nums[objpos], nums[left], nums[right]});
                    // 不漏
                    ++left;
                    --right;
                    // 去重
                    while(left < right && nums[left] == nums[left - 1])
                        ++left;
                    while(left < right && nums[right] == nums[right + 1])
                        --right;
                }
            }
            ++objpos;
            // 去重
            while(objpos <= nums.size() - 3 && nums[objpos] == nums[objpos - 1])
                ++objpos;
        }
        return ret;
    }
};