LeetCode Q18: 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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

Extended from 3Sum, fixed the first pointer, and for the last three pointers, solve the problem use 3Sum. 

Solution:
This problem can be downgraded to 3Sum then to 2Sum problem. We will solve the most inner loop using two pointers. For all other loops, we linearly scanning over the given array. The trick here is that in each loop, we skip over identical elements which are not seen the first time.

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int> > results;
	if(nums.size()<=3)
	return results;
	sort(nums.begin(), nums.end());
	for(int i0=0; i0<=nums.size()-4; i0++){
	int v0=nums[i0];
	if(i0!=0&&nums[i0]==nums[i0-1])
	continue;
	for(int i1=i0+1; i1<=nums.size()-3; i1++){
	int v1=nums[i1];
	if(i1!=i0+1&&nums[i1]==nums[i1-1])
	continue;
	int i2=i1+1;
	int i3=nums.size()-1;
	while(i2<i3){
	int v2=nums[i2];
	int v3=nums[i3];
	if(i2>i1+1&&nums[i2]==nums[i2-1]){i2++;continue;}
	if(i3<nums.size()-1&&nums[i3]==nums[i3+1]){i3--;continue;}
	int r=v0+v1+v2+v3;
	if(r>target){i3--; continue;}
	if(r<target){i2++; continue;}
	if(r==target){
	vector<int> r={v0, v1, v2, v3};
	i2++;
	i3--;
	results.push_back(r);
	continue;
	}
	}
	}
	}
	return results;
	}
	};

view raw Q184Sum.cpp hosted with ❤ by GitHub