BM54. [三数之和]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM54. 三数之和

https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=295&sfm=discuss&channel=nowcoder

题目主要信息:

• 给定一个长度为的数组，要找出其中所有满足相加等于0的三元组，即数组中所有三个相加为0的数集
• 三元组内部必须非降序排列，且三元组不能有重复

具体思路:

• step 1：排除边界特殊情况。
• step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。
• step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。
• step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有；如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明左指针太小了，将其右移扩大，直到两指针相遇，剩余子数组找完了。

注：对于三个数字都要判断是否相邻有重复的情况，要去重。

具体过程如下图所示：

代码实现:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        int n = num.size();
        if(n < 3) //不够三元组
            return res;
        sort(num.begin(), num.end()); //排序
        for(int i = 0; i < n - 2; i++){
            if(i != 0 && num[i] == num[i - 1])
                continue;
            int left = i + 1; //后续的收尾双指针
            int right = n - 1;
            int target = -num[i]; //设置当前数的负值为目标
            while(left < right){
                if(num[left] + num[right] == target){//双指针指向的二值相加为目标，则可以与num[i]组成0
                    res.push_back({num[i], num[left], num[right]});
                    while(left + 1 < right && num[left] == num[left + 1])
                        left++; //去重
                    while(right - 1 > left && num[right] == num[right - 1])
                        right--; //去重
                    left++; //双指针向中间收缩
                    right--;
                }
                else if(num[left] + num[right] > target)//双指针指向的二值相加大于目标，右指针向左
                    right--;
                else left++;//双指针指向的二值相加小于目标，左指针向右
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，排序的复杂度为，查找三元组的复杂度为
• 空间复杂度：，res属于必要空间，不属于额外空间