【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] ]

 

枚举前两个(i,j)求后两个(k,t)，复杂度O(N^3)。在枚举前两个数的时候，有些情况一定不存在解，可直接跳过以节省时间 vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int n=nums.size(); vector< vector<int> > res; if(n<4)return res; for(int i=0;i<n-3;i++){ if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)break; if(nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target)continue; if(i>0 && nums[i]==nums[i-1])continue; for(int j=i+1;j<n-2;j++){ if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)break; if(nums[i]+nums[j]+nums[n-1]+nums[n-2]<target)continue; if(j>i+1 && nums[j]==nums[j-1])continue; for(int k=j+1,t=n-1;k<t;){ int sum=nums[i]+nums[j]+nums[k]+nums[t]; if(sum==target){ vector<int> temp(4); temp[0]=nums[i];temp[1]=nums[j]; temp[2]=nums[k];temp[3]=nums[t]; res.push_back(temp); while(k+1<t && nums[k+1]==nums[k])k++; k++; while(t-1>k && nums[t-1]==nums[t])t--; t--; } else if(sum<target){ while(k+1<t && nums[k+1]==nums[k])k++; k++; } else{ while(t-1>k && nums[t-1]==nums[t])t--; t--; } } } } return res; }