Skip to main content
deleted 111 characters in body
Source Link
Denis
  • 8.5k
  • 5
  • 31
  • 76

Hashset<T>.Add(..) wont add any duplicates items anyway it's checking thethat 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 check the length before adding the item and after adding the item. If they are different that means there is no such item inuse the returned boolean value from HashSetHashSet<T>.Add().

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]);
                    int previousCount = keys.Count;
                   if (keys.Add(triplet);
                    if (previousCount != keys.Count)
                    {
                        results.Add(new List<int> {triplet.A, triplet.B, triplet.C});
                    }
                    start++;
                    end--;
                }
                else
                {
                    end--;
                }
            }
            else
            {
                start++;
            }
        }
    }
    return results;
}

Hashset<T>.Add(..) wont add any duplicates items anyway it's checking the 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 check the length before adding the item and after adding the item. If they are different that means there is no such item in the HashSet.

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]);
                    int previousCount = keys.Count;
                    keys.Add(triplet);
                    if (previousCount != keys.Count)
                    {
                        results.Add(new List<int> {triplet.A, triplet.B, triplet.C});
                    }
                    start++;
                    end--;
                }
                else
                {
                    end--;
                }
            }
            else
            {
                start++;
            }
        }
    }
    return results;
}

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().

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;
}
Source Link
Denis
  • 8.5k
  • 5
  • 31
  • 76

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

enter image description here

Here are the original results with your code :

enter image description here

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 the 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 check the length before adding the item and after adding the item. If they are different that means there is no such item in the HashSet.

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]);
                    int previousCount = keys.Count;
                    keys.Add(triplet);
                    if (previousCount != keys.Count)
                    {
                        results.Add(new List<int> {triplet.A, triplet.B, triplet.C});
                    }
                    start++;
                    end--;
                }
                else
                {
                    end--;
                }
            }
            else
            {
                start++;
            }
        }
    }
    return results;
}