Skip to main content
added 183 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41

Even faster. Bring the last until you are at target or less.
No purpose to starting at the end with the last as if one of the first two is increased then last has to decrease

Even faster. Bring the last until you are at target or less.
No purpose to starting at the end with the last as if one of the first two is increased then last has to decrease

added 7 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41

I am getting like 8x faster than yourOP solution using

I am getting like 8x faster than your using

I am getting like 8x faster than OP solution using

added 2613 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41

This should faster as it skips values already evaluated
Since it skips values evaluated then do not need to check for duplicate

public static IList<IList<int>> ThreeSumB(int[] nums)
{
    IList<IList<int>> results = new List<IList<int>>();           
    if (nums == null)
        return results;
    int length = nums.Length;
    if (length < 3)
        return results;
    Array.Sort(nums);
    Debug.WriteLine(string.Join(", ", nums));          
    int target = 0;
    int firstNo;
    int newTarget;
    int start;
    int end;
    for (int i = 0; i < length - 2; i++)
    {
        firstNo = nums[i];
        if (i > 0 && firstNo == nums[i-1])
            continue;
        // using two pointers to go through once the array, find two sum value 
        newTarget = target - firstNo;
        start = i + 1;
        end = length - 1;
        while (start < end)
        {
            int twoSum = nums[start] + nums[end];
            if (twoSum < newTarget)
            {
                //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
                start++;
                while (start < end && nums[start - 1] == nums[start])
                    start++;
                //Debug.WriteLine(nums[start]);
            }
            else if (twoSum > newTarget)
            {
                //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
                end--;
                while (start < end && nums[end + 1] == nums[end])
                    end--;
                //Debug.WriteLine(nums[end]);
            }
            else
            {
                results.Add(new List<int> { firstNo, nums[start], nums[end] });

                //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
                start++;
                while (start < end && nums[start - 1] == nums[start])
                    start++;
                //Debug.WriteLine(nums[start]);

                //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
                end--;
                while (start < end && nums[end + 1] == nums[end])
                    end--;
                // Debug.WriteLine(nums[end]);
            }
        }
    }
    return results;
}

I am getting like 8x faster than your using

int[] array = new int[] { -1, 0, 1, 2, -1, -4, -1, -4, 1, 2, 2 };

This should faster as it skips values already evaluated
Since it skips values evaluated then do not need to check for duplicate

public static IList<IList<int>> ThreeSumB(int[] nums)
{
    IList<IList<int>> results = new List<IList<int>>();           
    if (nums == null)
        return results;
    int length = nums.Length;
    if (length < 3)
        return results;
    Array.Sort(nums);
    Debug.WriteLine(string.Join(", ", nums));          
    int target = 0;
    int firstNo;
    int newTarget;
    int start;
    int end;
    for (int i = 0; i < length - 2; i++)
    {
        firstNo = nums[i];
        if (i > 0 && firstNo == nums[i-1])
            continue;
        // using two pointers to go through once the array, find two sum value 
        newTarget = target - firstNo;
        start = i + 1;
        end = length - 1;
        while (start < end)
        {
            int twoSum = nums[start] + nums[end];
            if (twoSum < newTarget)
            {
                //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
                start++;
                while (start < end && nums[start - 1] == nums[start])
                    start++;
                //Debug.WriteLine(nums[start]);
            }
            else if (twoSum > newTarget)
            {
                //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
                end--;
                while (start < end && nums[end + 1] == nums[end])
                    end--;
                //Debug.WriteLine(nums[end]);
            }
            else
            {
                results.Add(new List<int> { firstNo, nums[start], nums[end] });

                //Debug.WriteLine(nums[start] + " " + nums[start + 1]);
                start++;
                while (start < end && nums[start - 1] == nums[start])
                    start++;
                //Debug.WriteLine(nums[start]);

                //Debug.WriteLine(nums[end] + " " + nums[end - 1]);
                end--;
                while (start < end && nums[end + 1] == nums[end])
                    end--;
                // Debug.WriteLine(nums[end]);
            }
        }
    }
    return results;
}

I am getting like 8x faster than your using

int[] array = new int[] { -1, 0, 1, 2, -1, -4, -1, -4, 1, 2, 2 };
added 283 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
deleted 218 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
deleted 1694 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
added 53 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
uh on, == not !=
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
added 88 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
added 1769 characters in body
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading
Source Link
paparazzo
  • 6k
  • 3
  • 19
  • 41
Loading