leetcode 链接：三数之和

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = []
输出：[]

输入：nums = [0]
输出：[]

解答 & 代码

题目要求三元组之间不重复，因此可以通过如下两个操作来保证不重复：

• 设三元组为 (a, b, c)，在枚举三元组时，保证 a<=b<=c
  • 实现方法：先将数组按升序排序
• 对于三元组的元素，比如 a，如果上一次 a 的取值和当前 a 的取值相同，则跳过这个 a 的取值，继续取下一个值；对于 b，c 同理
  • eg. 排序后的数组为 [-1, -1, 0, 1, 1, 2]，上一次将第 0 个元素作为 a 的值，即 -1，这一次用第 1 个元素作为 a 的值，还是 0，就重复了，让 a 取下一个值 0

另外，寻找 b，c 的过程其实可以是并列的，不需要两重循环，让 b 的指针往右移，c 的指针往左移

一共两重循环（寻找 a 一重，寻找 b、c 一重），时间复杂度 O()，数组排序时间复杂度 O(N logN)，总时间复杂度 O()

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int targetSum = 0;                    // 目标和，本题为 0

        vector<vector<int>> ansList;        // 存储答案

        sort(nums.begin(), nums.end());        // 现将数组排序（升序）
        int size = nums.size();
        for(int firstIdx = 0; firstIdx < size; ++firstIdx)
        {
            // 如果第一个数就大于目标和，往后都没法找到三个数和为targetSum了，因为是递增数组
            if(nums[firstIdx] > targetSum)
                return ansList;
            // 去重：如果第一个数下标不是 0，并且和前面取过的数相同，跳过本次循环取下一个数
            if(firstIdx > 0 && nums[firstIdx] == nums[firstIdx - 1])
                continue;

            // 使用双指针在第一个数后面的区间寻找另外两个数
            int secondIdx = firstIdx + 1;    // 第二个数的下标，初始为第一个数的后一个数
            int thirdIdx = size - 1;        // 第三个数的下标，初始位数组的最后一个数
            while(secondIdx < thirdIdx)
            {
                // 去重
                if(secondIdx > firstIdx + 1 && nums[secondIdx] == nums[secondIdx - 1])
                {
                    ++secondIdx;
                    continue;
                }                    
                if(thirdIdx < size - 1 && nums[thirdIdx] == nums[thirdIdx + 1])
                {
                    --thirdIdx;
                    continue;
                }

                // 如果三元组的和超过了目标和，则让第三个数的指针左移
                if(nums[firstIdx] + nums[secondIdx] + nums[thirdIdx] > targetSum)
                    --thirdIdx;
                // 如果三元组的和小于目标和，则让第二个数的指针右移
                else if(nums[firstIdx] + nums[secondIdx] + nums[thirdIdx] < targetSum)
                    ++secondIdx;
                // 如果三元组的和等于目标和
                else
                {
                    // 添加到答案中
                    ansList.push_back(vector<int>{nums[firstIdx], nums[secondIdx], nums[thirdIdx]});
                    // 继续寻找下一组三元组
                    ++secondIdx;
                    --thirdIdx;
                }
            }
        }

        return ansList;
    }
};

执行结果：

执行结果：通过

执行用时：128 ms, 在所有 C++ 提交中击败了 28.68% 的用户
内存消耗：19.5 MB, 在所有 C++ 提交中击败了 57.00% 的用户