Simple C# solution with explanation


  • 0
    *

    public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {

    	nums = nums.OrderBy (n => n).ToArray();
    	IList<IList<int>> result = new List<IList<int>>(){};
    	Dictionary<string, int> uniqueNumDict = new Dictionary<string, int>();
    	
    	
    	if(nums.Length < 3)
    		return result;
    	
    	for(int i=0; i<nums.Length-2; i++)
    	{
    		int current = i;
    		int start = i+1;
    		int end = nums.Length-1;
    		
    		while(start < end)
    		{
    			if((nums[current] + nums[start] + nums[end] == 0) && (!TripletExistsInResultSet(uniqueNumDict, nums[current], nums[start], nums[end])))
    			{
    				result.Add(new List<int>(){nums[current], nums[start], nums[end]});
    				end = end - 1;
    			}
    			if(nums[current] + nums[start] + nums[end] > 0)
    				end = end -1;
    			else
    				start = start + 1;
    		}
    	}
    	
    	return result;
    }
    
    
    // Check if the triplet exists. Ideally this is not required as, to test, we would never go over the same three elements. BUt in cases like "ThreeSum(new[]{-1,0,1,2,-1,-4})", the out (-1,0, 1) and (-1,0, 1) is present twice in the given array, however the question wants us to add this only once. SO we need this function. 
    public bool TripletExistsInResultSet(Dictionary<string, int> uniqueNumDict,  int first, int second, int third)
    {
    	int[] nums = new int[]{first, second, third};
    	Array.Sort(nums);
    	string uniqueKey = string.Join("", nums);
    	if(!uniqueNumDict.ContainsKey(uniqueKey))
    	{
    		uniqueNumDict.Add(uniqueKey, 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.