C# Accepted solution using Dictionary O(n^2)


  • 0
    J

    Get the list of negative numbers and positive numbers into two dictionaries, and then iterate through the possible combinations of two negative numbers and two positive numbers and check if the corresponding complement is present in the other dictionary. We need to check for zero as well, to handle certain cases.

    public IList<IList<int>> ThreeSum(int[] nums) 
        {
           var result = new List<IList<int>>();
            if (nums.Length < 3) return result;
            
            var zeropresent = false; var zerocount = 0;
            var negative = new Dictionary<int, int>();
            var positive = new Dictionary<int, int>();
            foreach (var num in nums)
            {
                if (num == 0)
                {
                    zeropresent = true;
                    zerocount++;
                }
                else if (num < 0)
                {
                    if (negative.ContainsKey(num)) negative[num]++;
                    else negative.Add(num, 1);
                }
                else
                {
                    if (positive.ContainsKey(num)) positive[num]++;
                    else positive.Add(num, 1);
                }
            }
            
            if (zeropresent)
            {
                if (zerocount >= 3) result.Add(new List<int>(){0,0,0});
                foreach (var negkey in negative.Keys)
                {
                    if (positive.ContainsKey(Math.Abs(negkey))) result.Add(new List<int>(){negkey, 0 , -negkey});
                }
            }
            
            var negativearray = negative.Keys.ToList().ToArray();
            for (int i = 0; i < negativearray.Length; i++)
            {
                var firstnum = negativearray[i];
                for (int j = i; j < negativearray.Length; j++)
                {
                    var secondnum = negativearray[j];
                    if (firstnum == secondnum)
                    {
                        if (negative[firstnum] > 1 && positive.ContainsKey(Math.Abs(2*firstnum)))
                            result.Add(new List<int>(){firstnum, firstnum, -2*firstnum});
                    }
                    else
                    {
                        if (positive.ContainsKey(Math.Abs(firstnum+secondnum)))
                            result.Add(new List<int>(){firstnum, secondnum, -(firstnum+secondnum)});
                    }
                }
            }
            
            var positivearray = positive.Keys.ToList().ToArray();
            for (int i = 0; i < positivearray.Length; i++)
            {
                var firstnum = positivearray[i];
                for (int j = i; j < positivearray.Length; j++)
                {
                    var secondnum = positivearray[j];
                    if (firstnum == secondnum)
                    {
                        if (positive[firstnum] > 1 && negative.ContainsKey(-(2*firstnum)))
                            result.Add(new List<int>(){firstnum, firstnum, -2*firstnum});
                    }
                    else
                    {
                        if (negative.ContainsKey(-(firstnum + secondnum)))
                            result.Add(new List<int>(){firstnum, secondnum, -(firstnum+secondnum)});
                    }
                }
            }
            
            return result; 
        }
    

Log in to reply
 

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