# C# - two solutions - O(n^2 logn) and O(n^2)

• Here are 2 solutions both rely on sorted array.

1. for each element, do 2 pointer search for a two sum completing the result, skip dupes.
2. for each element, do another for each higher index element and do a binary search through the remaining elements for the 3rd element to complete the result.

The two pointer approach is O(n^2) and did indeed preform better from OJ timer.

``````    public IList<IList<int>> ThreeSum(int[] nums)
{
return ThreeSum_TwoPointer(nums);
// return ThreeSum_BinarySearch(nums);
}

public IList<IList<int>> ThreeSum_TwoPointer(int[] nums)
{
Array.Sort(nums);
IList<IList<int>> lists = new List<IList<int>>();

for (int i = 0; i < nums.Length - 2; i++)
{
int left = i + 1;
int right = nums.Length - 1;
while (left < right)
{
if (nums[i] == 0 - nums[left] - nums[right])
{
lists.Add(new List<int>() { nums[i], nums[left], nums[right] });

// skip dupes
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;

left++;
right--;

}
else if (nums[i] < 0 - nums[left] - nums[right])
{
left++;
}
else
{
right--;
}
}

// skip dupes
while (i < nums.Length - 1 && nums[i] == nums[i+1]) i++;
}

return lists;
}

public IList<IList<int>> ThreeSum_BinarySearch(int[] nums)
{
Array.Sort(nums);
IList<IList<int>> lists = new List<IList<int>>();

for (int i = 0; i < nums.Length - 2; i++)
{
for (int j = i + 1; j < nums.Length - 1; j++)
{
int left = j + 1;
int right = nums.Length - 1;
while (left <= right)
{
int mid = (left + right)/2;
if (nums[mid] == 0 - nums[i] - nums[j])
{
lists.Add(new List<int>() { nums[i], nums[j], nums[mid] });
break;
}
else if (nums[mid] < 0 - nums[i] - nums[j])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}

// skip dupes
while (j < nums.Length - 1 && nums[j] == nums[j+1]) j++;
}

// skip dupes
while (i < nums.Length - 1 && nums[i] == nums[i+1]) i++;
}

return lists;
}
``````

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