18.4Sum

September 04, 2016

18.4Sum

Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

给出n个元素的数组S,寻找是否存在四个数组中的元素a,b,c,d且a+b+c+d=target,如果有,寻找出所有这样的不重复的四元组。

这道题如果有一个数是确定的,那么就转化为了3Sum问题,思路完全相同,代码上稍作改动即可

solution1 用时92ms

  • [ TODO To be faster]
/*solution 1*/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>>res;
        int left=0,mid1=0,mid2=0,right=0,tmp_mid2=0,tmp_right=0,tmp_mid1=0,tmp_left=0;
        int size=nums.size();
        sort(nums.begin(),nums.end());
        if(size<4)
            return res;
        for(left=0;left<size-3;left++){
            int tmp_left=target-nums[left];
            /*去除left造成的重复*/
			if(left > 0 && nums[left] == nums[left-1])
                continue;
            for(mid1=left+1;mid1<size-2;mid1++){
                int tmp=tmp_left-nums[mid1];
                mid2=mid1+1;
                right=size-1;
                /*去除mid1造成的重复*/
				if(mid1 > left+1 && nums[mid1] == nums[mid1-1])
                    continue;
                while(mid2<right){
                    if(nums[mid2]+nums[right]==tmp){
                        tmp_mid2=nums[mid2];
                        tmp_right=nums[right];
                        vector<int>quadruplets(4,0);
                        quadruplets[0]=nums[left];
                        quadruplets[1]=nums[mid1];
                        quadruplets[2]=nums[mid2];
                        quadruplets[3]=nums[right];
                        res.push_back(quadruplets);
                        while(mid2 < right && nums[++mid2] == tmp_mid2);/*去除mid2造成的重复*/
                        while(mid2 < right && nums[--right] == tmp_right);
                    }
                    else if(nums[mid2]+nums[right]<tmp)
                        mid2++;
                    else
                        right--;
                }
            }
        }
        return res;
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017