18. 4Sum[M]四数之和

题目

Given an array nums of n integers and an integer target, are there elements a, b, c and d in nums such that a+ b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0 -1, 0, -2, 2], and target = 0.

A solution set is:

[

 [-1, 0, 0, 1],

 [-2, -1, 1, 2],

 [-2, 0, 0, 2]

]

---

思路

本题思路很简单，有了前面3Sum的基础，这里只要将 target-d，然后就是3Sum的解题方法。

---

C++

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

        vector<vector<int> > result;

        if(nums.size() < 4)

            return result;

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

        int pMid = 0;

        int pEnd = 0;

        for(int i = 0;i<nums.size() - 3; i++){

            //转化成3Sum问题

            int subTarget=target - nums[i];

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

                continue;

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

                int subTarget2 = subTarget - nums[j];

                pMid = j + 1;

                pEnd = nums.size() - 1;

                if(j > i + 1 && nums[j] == nums[j-1])

                    continue;

                while(pMid < pEnd){

                    int sum1 = nums[pMid] + nums[pEnd];

                    if(sum1 < subTarget2){

                        pMid ++;

                    }

                    else if(sum1 > subTarget2){

                        pEnd --;

                    }

                    else{

                        vector<int> tempVec(4,0);

                        tempVec[0] = nums[i];

                        tempVec[1] = nums[j];

                        tempVec[2] = nums[pMid];

                        tempVec[3] = nums[pEnd];

                        result.push_back(tempVec);

                        while(pMid < pEnd && nums[pMid] == nums[pMid+1]) //去除重复元素

                            pMid ++;

                        while(pMid < pEnd && nums[pEnd] == nums[pEnd -1])

                            pEnd --;

                        pMid ++;

                        pEnd --;

                    }

                }

            }

        }

        return result;

    }

Python