Simple C# Soltuion with explanation


  • 0
    *

    public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
    // Sort the given array.
    nums = nums.OrderBy(n => n).ToArray();
    IList<IList<int>> result = new List<IList<int>>(){};
    Dictionary<string, int> uniqueQuadrupletDict = new Dictionary<string, int>(){};

    	if(nums.Length < 4)
    		return result;
    	
        for(int i=0; i<nums.Length-3; i++)
    	{
    		for(int j=i+1; j<nums.Length-2; j++)
    		{
    			int start = j+1;
    			int end = nums.Length-1;
    			
    			while(start < end)
    			{
    				if((nums[i]+nums[j]+nums[start]+nums[end] == target) && (!QuadrupletExists(uniqueQuadrupletDict, nums[i], nums[j], nums[start], nums[end])))	
    					result.Add(new List<int>(){nums[i], nums[j], nums[start], nums[end]});
    				if(nums[i]+nums[j]+nums[start]+nums[end] > target)	
    					end = end -1;
    				else
    					start = start +1;
    			}
    		}
    	}
    	
    	return result;
    }
    
    private bool QuadrupletExists(Dictionary<string, int> uniqueQuadrupletDict, int first, int second, int third, int fourth)
    {
    	int[] quadrupleList = new int[] {first, second, third, fourth};
    	
    	Array.Sort(quadrupleList);
    	
    	string quadruple = string.Join("", quadrupleList);
    	
    	if(!uniqueQuadrupletDict.ContainsKey(quadruple))
    	{
    		uniqueQuadrupletDict.Add(quadruple, 1);
    		return false;
    	}
    	
    	return true;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.