leetcode-15. 三数之和

题目

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

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

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

3刷 2022 07 27

• 排序
• while循环中去重，是对nums[left]和nums[right]去重
• for循环最后也要去重，是对nums[i]去重
• while中的顺序，先保存三元组到res中，然后双指针收缩，再去重

class Solution {
public:
/*
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
*/
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 先排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;

        for (int i = 0; i < nums.size(); i++)
        {
            int t = nums[i];
            int left = i + 1, right = nums.size() - 1;

            while (left < right)
            {
                if (t + nums[left] + nums[right] > 0) 
                    right--;
                else if (t + nums[left] + nums[right] < 0) 
                    left++;
                else
                {
                    // 保存三元组
                    vector<int> tmp = {t, nums[left], nums[right]};
                    res.push_back(tmp);
                    
                    // 找到答案后，双指针同时收缩
                    left++;
                    right--;

                    // 去重
                    // 如果left指针移动后，值仍等于原来的，就说明是重复的值，即 nums[left] = nums[left-1]，应该跳过
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }
            }

            // 对num[i]去重
            while (i <= nums.size() - 1 - 1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
};

思路

将求 三数之和 转换为 求两数之和，先把数组排序，找第一个数x作为3数中的一个数字，后面只需要找到其他的2个数的和加上这个数x等于0就行。
即找到：a+b+x=0, a+b = -x, 令 sum = -x, 则求 a + b = sum
然后就是求2数之和等于sum了。使用双指针。

不过要注意重复元素的情况；有三种情况重复,

• nums[left]元素重复，left++后要判断元素是否重复；
• nums[right]元素重复，right–后要判断是否重复；
• nums[a]元素是否重复，要先判断num[a] == num[a+1]是否重复，再进行跳过重复元素的操作a++.

2刷 20220623

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        sort(nums.begin(), nums.end());

        for (int a = 0; a < nums.size(); a++)
        {
            int sum = -nums[a];

            int left = a + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] < sum)
                    left++;
                else if (nums[left] + nums[right] > sum)
                    right--;
                else if (nums[left] + nums[right] == sum)
                {
                    vector<int> tmp = {nums[a], nums[left], nums[right]};
                    res.push_back(tmp);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }
            }

            while (a + 1 <= nums.size() - 1 && nums[a] == nums[a+1]) a++; 
        }

        return res;
    }
};

---

1刷 20220622

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //先排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;

        for (auto x : nums) cout << x << " ";
        cout << endl;

        for (int a = 0; a < nums.size(); a++)
        {
            int sum = -nums[a];
            // 找 两数之和=sum， 使用双指针

            int left = a + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] < sum) left++;
                else if (nums[left] + nums[right] > sum) right--;
                else if (nums[left] + nums[right] == sum)
                {
                    // 把 nums[left], nums[right], nums[a] 保存下来
                    vector<int> tmp{nums[left], nums[right], nums[a]};
                    res.push_back(tmp);
                    left ++;
                    right --;
                    // 去除重复
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }
            }

            // 去重
            while (a + 1 < nums.size() && nums[a] == nums[a+1])
                a++;
        }

        return res;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。