力扣15:三数之和

题目

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

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

思路

如果仅仅是三数之和那我们可以和两数之和相同使用嵌套循环来得到三元组解，但是题目特意要求了不可以包含重复的三元组，如果只是两个数我们还可以使用哈希表来排除重复的二元组。但三元组我们就不好使用哈希来排除重复解了并且三次嵌套的时间复杂度太高了也不好使用。那我们是否可以将三次嵌套改成二次嵌套呢？也就是我们使用一层循环确认一个数再用第二层循环确定另外两个数，第一层循环好说我们直接遍历数组即可也就可以确定一个数主要是第二层循环要如何确定两个数呢？观察题目我们发现数组是无序的这也就导致我们对重复解的排查工作很难进行，那么我们是否可以将数组进行排序，这样我们在第一层里确定了第一个数在第二层里只要使用双指针即一个指向第一个数的后一位一个指向数组的最后一位，再通过对三数相加与0的比较就可以确定三元组的解。而且在排序了之后我们就可以直接跳过与当前值相同的位置了。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if (n < 3) {
            return res;
        }
        // 排序
        sort(nums.begin(), nums.end());
        //第一层循环
        // 第一个数
        for (int i = 0; i < n; i++) {
            // 因为已经排序了如果第一个数都大于0
            // 那么就没有解了
            if (nums[i] > 0) {
                return res;
            }
            //如果i的当前值等于i-1的值就跳过
            //因为会导致重复解
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 第二个数
            int left = i + 1;
            // 第三个数
            int right = n - 1;
            //第二层循环
            //left要始终小于right
            while (left < right) {
                //如果三个数相加等于0，就得出一个三元组解
                if (nums[i] + nums[left] + nums[right] == 0) {
                    vector<int> three_nums;
                    three_nums.push_back(nums[i]);
                    three_nums.push_back(nums[left]);
                    three_nums.push_back(nums[right]);
                    res.push_back(three_nums);
                    //循环判断left的下一个位置的值是否等于当前值
                    //避免重复解
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    //与left相同，避免重复解
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    //left和right的下一个位置的值和当前值不重复
                    //就一个++一个--
                    left++;
                    right--;
                //如果三数相加小于0就说明left小了
                //因为第一个数是固定的，只能移动left和right
                //又因为数组已经进行排序了
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                //大于0了就让right--
                } else {
                    right--;
                }
            }
        }
        return res;
    }
};