LeetCode #15：Three Sum(三数之和)

题目描述

首先将数组排序，然后通过一层 for 循环枚举数组元素，i 从下标 0 的地方开始，同时定义指针 left 在 i+1 的位置上，定义指针 right 在数组结尾的位置上。

根据题意，我们需要数组中找到 abc 使得 a + b + c = 0，我们指定 a = nums[i]，b = nums[left]，c = nums[right]。当 nums[i] + nums[left] + nums[right] > 0 时，right 指针左移（此时三数之和大于零，由于数组先前排好了序，将 right 左移才有可能使得和为 0）；同理当 nums[i] + nums[left] + nums[right] < 0 时 left 指针右移；当 nums[i] + nums[left] + nums[right] == 0 时，将三元组 (nums[i], nums[left], nums[right] )放入最终结果中，将左右两边和 nums[left]、nums[right] 相等数去重后同时将 left 指针右移、right 指针左移，继续寻找下一个答案。

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

        for(int i = 0; i < nums.size(); i ++) {
            if(nums[i] > 0) // 若排序后最小的数还是大于零的，那么这个序列肯定不存在三个元素相加等于0
                return res;
            
            if(i > 0 && nums[i] == nums[i - 1]) // 对nums[i]去重。不能写作nums[i] == nums[i + 1]，这样会漏掉诸如(-1, -1, 2)的答案，因为题目要求不能有重复的三元组，但三元组内的元素是可以重复的
                continue;

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

                    //对left和right边界元素降重
                    while (right > left && nums[right] == nums[right - 1]) 
                        right--;
                    while (right > left && nums[left] == nums[left + 1]) 
                        left++;

                    left ++;
                    right --;
                }
            }
        }

        return res;
    }
};