Leetcode 15. 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: 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]
]


I did review Leetcode 3 sum algorithm a few hours, and put together the following C# code. The time complexity is optimal, \$O(n*n)\$ where \$n\$ is the length of the array, pass Leetcode online judge. Also, I did a few improvements, make it more flat (using two continue statements, instead of if/else statements), test cases are added, two sum algorithm uses two pointer technique to go through the array once.

Please share your ideas to improve C# code.

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_15_3Sum
{
/*
*
* Work on this 3 sum algorithm
*
* Leetcode 15: 3 sum
* https://leetcode.com/problems/3sum/
*
* 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)
*
*/
class Program
{
static void Main(string[] args)
{
// test 3 sum
// 2 lists, one is -1, 0, 1, second one is -1, -1, 2
int[] array = new int[6] { -1, 0, 1, 2, -1, -4 };

IList> triplets = ThreeSum(array);

Debug.Assert(triplets.Count == 2);
Debug.Assert(String.Join(",", triplets[0].ToArray()).CompareTo("-1,-1,2") == 0);
Debug.Assert(String.Join(",", triplets[1].ToArray())

Just a few tips about your PrepareKey method.

private static string PrepareKey(int[] arr, int length)
{
  string key = string.Empty;

  for (int j = 0; j < length; j++)
  {
      key += arr[j].ToString();
      key += ",";
  }

  return key;
}

The entire function can be replaced with:

string.Join(",", arr);

but in cases where you need to build a string with a loop you should use the StringBuilder next time because it's much faster then concatenating strings with the + operator.

for (int j = 0; j < length; j++)

You could also the the foreach loop for this as arrays are enumerable.

PrepareKey(int[] arr, int length)

This method does not need the length parameter because an array has a Length property.

StackExchange Code Review Q#150920, answer score: 8