Return to Revisions

I offer a different approach which got accepted on Leetcode with the following results

Here are the original results with your code :

As you can see my soltion wins by ~100 ms.

I prefer having a class with overloaded equality checks so that it can be used in the Hashset to determine if an item is duplicate or not. I also replaced this line :

if (!keys.Contains(key))

To this

int previousCount = keys.Count;
keys.Add(triplet);
if (previousCount != keys.Count)

Hashset<T>.Add(..) wont add any duplicates items anyway it's checking that internally but we still need to know if the item is actually duplicate to see if we need to add it to the results I prefer not checking if the key is contained but rather use the returned boolean value from HashSet<T>.Add().

Here is my solution :

internal class Triplet
{
    public int A { get; }
    public int B { get; }
    public int C { get; }

    public Triplet(int a, int b, int c)
    {
        A = a;
        B = b;
        C = c;
    }

    public static bool operator ==(Triplet first, Triplet second)
    {
        return first.A == second.A && first.B == second.B && first.C == second.B;
    }

    public static bool operator !=(Triplet first, Triplet second)
    {
        return !(first == second);
    }

    protected bool Equals(Triplet other)
    {
        return A == other.A && B == other.B && C == other.C;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Triplet)obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            var hashCode = A;
            hashCode = (hashCode * 397) ^ B;
            hashCode = (hashCode * 397) ^ C;
            return hashCode;
        }
    }
}

And this is the actual algorithm :

public static IList<IList<int>> ThreeSum(int[] nums)
{
    IList<IList<int>> results = new List<IList<int>>();
    HashSet<Triplet> keys = new HashSet<Triplet>();

    if (nums == null || nums.Length == 0)
        return results;

    Array.Sort(nums);

    int length = nums.Length;

    int target = 0;
    for (int i = 0; i < length - 2; i++)
    {
        int firstNo = nums[i];

        // using two pointers to go through once the array, find two sum value 
        int newTarget = target - firstNo;
        int start = i + 1;
        int end = length - 1;

        while (start < end)
        {
            int twoSum = nums[start] + nums[end];

            if (twoSum >= newTarget)
            {
                if (twoSum <= newTarget)
                {
                    Triplet triplet = new Triplet(firstNo, nums[start], nums[end]);
                    if (keys.Add(triplet))
                    {
                        results.Add(new List<int> {triplet.A, triplet.B, triplet.C});
                    }
                    start++;
                    end--;
                }
                else
                {
                    end--;
                }
            }
            else
            {
                start++;
            }
        }
    }
    return results;
}