LeetCode——18. 4Sum

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一.题目链接：https://leetcode.com/problems/4sum/

二.题目大意：

给定一个数组A和一个目标值target，要求从数组A中找出4个数来使之构成一个4元祖，使得这四个数的和等于target，找出所有的四元组，当然这些四元组不能有重复的。

三.题解：

这道题实质就是3sum的变形，关于4sum问题，已经在https://www.cnblogs.com/wangkundentisy/p/9079622.html这里说过了，无外乎最外面两层循环，最里面的循环使用哈希表或者双指针，此处使用的是双指针法。具体代码如下：

class Solution

{

public:

    vector<vector<int>> fourSum(vector<int>& nums, int target)

    {

        int len = nums.size();

        vector<vector<int>> rs;

        if(len < 4)

            return rs;

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

        for(int i = 0; i < len; i++)

        {

            if(i != 0 && nums[i] == nums[i - 1])

                continue;

            for(int j = i + 1; j < len - 1; j++)

            {

                if(j != i + 1 && nums[j] == nums[j -1])//注意此处的去重，要保证j不是第一次被使用，所以必须是j!=i+1

                    continue;

                int l = j + 1, r = len - 1;

                while(l < r)

                {

                    if(nums[i] + nums[j] + nums[l] + nums[r] == target)

                    {

                        rs.push_back({nums[i],nums[j],nums[l],nums[r]});

                        l++;

                        r--;

                        while( l < r && nums[l] == nums[l - 1])

                            l++;

                        while(l < r && nums[r] == nums[r + 1])

                            r--;

                    }

                    else if(nums[i] + nums[j] + nums[l] + nums[r] < target)

                        l++;

                    else

                        r--;

                }

            }

        }

        return rs;

    }

};