3 SUM

Problem Statement

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Source: https://leetcode.com/problems/3sum/
Programming Language: C#
Run Time Complexity: O(n^2)

After sorting the input array, 3 three pointers are initialized.
The first pointer goes from index 0 to index end-2.
The 2nd pointers goes from the current element(1st pointer) index + 1
The 3rd pointers goes from the last element in a reverse order.

Two iterations:
1. 1st pointer from 0 to index end-2
2. while (2nd<3rd)

Conditions:
1. if (array[1st]+array[2nd]+array[3rd]==0), get one result
2. if (array[1st]+array[2nd]+array[3rd]>0), 3rd -1
3. if (array[1st]+array[2nd]+array[3rd]<0), 2nd +1

Solution

public IList<IList<int>> ThreeSum(int[] num)
{
    IList<IList<int>> Resultset3Sum = new List<IList<int>>();

    if ((num == null) || (num.Length < 3))
        return Resultset3Sum;

    // sort array
    List<int> numList = num.ToList();
    numList.Sort();

    for (int i = 0; i < numList.Count - 2; i++)
    {
        // //avoid duplicate solutions
        if (i == 0 || numList[i] > numList[i - 1])
        {

            int start = i + 1;
            int end = numList.Count - 1;

            while (start < end)
            {
                //case 1
                if (numList[i] + numList[start] + numList[end] == 0)
                {
                    List<int> temp = new List<int>();
                    temp.Add(numList[i]);
                    temp.Add(numList[start]);
                    temp.Add(numList[end]);

                    Resultset3Sum.Add(temp);
                    start++;
                    end--;
                    
                    //avoid duplicate solutions
                    while (start < end && numList[end] == numList[end + 1])
                        end--;

                    while (start < end && numList[start] == numList[start - 1])
                        start++;                    
                }
                //case 2
                else if (numList[i] + numList[start] + numList[end] < 0)
                {
                    start++;                    
                }
                //case 3
                else
                {
                    end--;
                }
            }
        }
    }
    return Resultset3Sum;
}