LeetCode(C++)刷题计划：15-三数之和

15-三数之和

@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com

Category	Difficulty	Pass rate	Tags	Companies
algorithms	Medium	24.31%	array / two-pointers	adobe / amazon / bloomberg / facebook / microsoft

1. 题目

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum/

2. 解法

2.1 解法一：双指针法

首先对数组从大到小排序，数组的大小为 n 。
固定一个数，从其右侧的数中寻找另外两个数。
假设我们固定的数为 nums[k], k = 0 to n-1 , 另外两个数初始时分别为 nums[l], nums[r] , 其中 l = k + 1, r = n - 1 。
令 sum = nums[k] + nums[l] + nums[r] 。
1. 若 sum < 0 ，则我们要增大 sum ，此时只能对 l 向右挪一格，即：l ++ 。
2. 若 sum > 0 ，则我们要减小 sum ，此时只能对 r 向左挪一格，即：r -- 。
3. 若 sum == 0 ，此时这三个数就我们需要的数，将他们加入结果里。此时，l 和 r 之间的数还可能有我们需要的数，我们此时需要左右都向内移动，即：l ++, r -- 。。
避免重复的数据。
1. 当 sum == 0 时，我们需要 l 和 r 都向内移动。此时需要过滤掉和当前 nums[l], nums[r] 重复的数据，我们巧妙的使用了两个while循环，同时需注意 l 要一直小于 r。
  while (l < r && nums[l] == nums[++ l]) { }
  while (l < r && nums[r] == nums[-- r]) { }
2. 同时，我们也要在 k 的循环中过滤掉和当前 nums[k] 重复的数字。这里的 k < len - 2主要是防止数组越界。
  while (k < len - 2 && nums[k] == nums[++ k]) { }
当 l >= r 时，说明与当前固定的 nums[k] 相组合的两个数已经找完，所以要进入下一个 nums[k]。

执行用时: 112 ms, 在所有 cpp 提交中击败了98.73%的用户
内存消耗: 14.6 MB, 在所有 cpp 提交中击败了86.17%的用户

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int len = nums.size();
        if (len < 3) {
            return res;
        }
        sort(nums.begin(), nums.end());
        int k = 0;
        while(k < len - 2 && nums[k] <= 0) {
            int l = k + 1;
            int r = len - 1;
            while (l < r) {
                int sum = nums[k] + nums[l] + nums[r];
                if (sum == 0) {
                    res.push_back({nums[k], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[++ l]) { }
                    while (l < r && nums[r] == nums[-- r]) { }
                }
                else if (sum < 0) {
                    ++ l;
                }
                else {
                    -- r;
                }
            }
            while (k < len - 2 && nums[k] == nums[++ k]) { }
        }
        return res;
    }
};