【力扣-哈希表】8、四数之和（18）

输入： nums = [1,0,-1,0,-2,2], target = 0
输出： [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
复制代码

输入： nums = [2,2,2,2,2], target = 8
输出： [[2,2,2,2]]
复制代码

// 参考三指针的方法
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        // 先进性排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;

        // 遍历
        for (int i = 0; i < nums.size(); i++)
        {
            // 下面的这种剪枝是错误的 ， 因为可能要求的target是负值，而且小于每一个元素
            // 上面的这种情况就会导致返回空数组
            // if (nums[i] > target)
            // {
            //     continue;
            // }

            // 第一个数已经出现过了，去重处理
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            for (int j = i + 1; j < nums.size(); j++)
            {

                // j对应的数已经出现过了 ，所以也做去重处理
                if (j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }

                // 设置左右指针
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right)
                {
                    // leetcode设置了限制用例 [1000000000,1000000000,1000000000,1000000000]
                    // 已经超出了整数的范围，所以这里使用相减的方式
                    // 或者使用long long int
                    if (nums[i] + nums[j] - target > -(nums[left] + nums[right]))
                    {
                        right--;
                    }
                    else if (nums[i] + nums[j] - target < -(nums[left] + nums[right]))
                    {
                        left++;
                    }
                    else
                    {
                        // 找到了四个数时，将其加入到结果数组中
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        // 对右指针去重处理
                        while (right > left && nums[right] == nums[right - 1])
                        {
                            right--;
                        }
                        // 对做指针去重处理
                        while (right < left && nums[left] == nums[left + 1])
                        {
                            left++;
                        }
                        // 找到一组数字后，左指针右移，右指针左移
                        right--;
                        left++;
                    }
                }
            }
        }
        return ret;
    }
};