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.
Notice that the solution set must not contain duplicate quadruplets.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Example 2:
Input: nums = [], target = 0 Output: []
Constraints:
0 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109
public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
Array.Sort(nums);
var res = new List<IList<int>>();
var set = new HashSet<string>();
for(int i=0;i<nums.Length-3;i++){
for(int j=i+1;j<nums.Length-2;j++){
for(int k=j+1, l=nums.Length-1;k<l;){
int sum = nums[i]+nums[j]+nums[k]+nums[l];
if(sum == target){
if(!set.Contains(GetKey(nums[i],nums[j],nums[k],nums[l]))){
set.Add(GetKey(nums[i],nums[j],nums[k],nums[l]));
res.Add(BuildList(nums[i],nums[j],nums[k],nums[l]));
}
k++;
}
else if(sum>target){
l--;
}
else if(sum<target){
k++;
}
}
}
}
return res;
}
private string GetKey(int a, int b, int c, int d){
return a.ToString()+":"+b.ToString()+":"+c.ToString()+":"+d.ToString();
}
private List<int> BuildList(int a, int b, int c, int d){
var res = new List<int>();
res.Add(a);
res.Add(b);
res.Add(c);
res.Add(d);
return res;
}
}Time Complexity: O(n^3)
Space Complexity: O(n)
