four sum

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> vecArr;
        if(nums.size()<4)
            return vecArr;

        sort(nums.begin(),nums.end());
        vector<int> vecElement;
       
        int num1 = INT_MIN;
        int num2 = INT_MIN;

        for(int iLoop1=0;iLoop1<nums.size();iLoop1++)
        {
            if(nums[iLoop1]==num1)
                continue;
            num1 = nums[iLoop1];
           
            for(int iLoop2=iLoop1+1;iLoop2<nums.size();iLoop2++)
            {
                if(num2==nums[iLoop2])
                    continue;
                num2 = nums[iLoop2];

                int sum12 = num1+num2;
                int target34 = target-sum12;
               
                //find 3 and 4
                int iLeft = iLoop2+1;
                int iRight = nums.size()-1;
               
                if(iLeft<iRight){
                    if(nums[iLeft]<<1 > target34 || nums[iRight]<<1 < target34)
                        continue;
                }
               
                while(iLeft<iRight){
                    int sum34 = nums[iLeft]+nums[iRight];
                    if(sum34==target34){
                        vecElement.clear();
                        vecElement.push_back(num1);
                        vecElement.push_back(num2);
                        vecElement.push_back(nums[iLeft]);
                        vecElement.push_back(nums[iRight]);
                       
                        vecArr.push_back(vecElement);
                       
                        int currentNum3 = nums[iLeft];
                        while(iLeft < iRight && nums[iLeft]==currentNum3)
                            iLeft++;
                       
                        int currentNum4 = nums[iRight];
                        while(iLeft < iRight && nums[iRight]==currentNum4)
                            iRight--;
                    }
                    else if(sum34<target34)
                        iLeft++;
                    else
                        iRight--;
                }
            }
            num2 = INT_MIN;
        }
        return vecArr;
    }
};

  

原文地址:https://www.cnblogs.com/dongfangchun/p/7200676.html