using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("******** ThreeSum ********");

        var result =  ThreeSum(new int[] {-1, 0, 1, 2, -1, -4}, 0);

        Print(result);

        Console.WriteLine("\n******** ThreeSumWithDup ********");

        result =  ThreeSumWithDup(new int[] {-1, 0, 1, 2, -1, -4}, 0);

        Print(result);

    }

    private static List<List<int>> ThreeSum(int[] nums, int target)

    {

        var result = new List<List<int>>();

​

        Array.Sort(nums);

        for(int i = 0; i < nums.Length - 2; i++)

        {

            if(i == 0 || (i > 0 && nums[i] != nums[i - 1]))

            {

                int newTarget = target - nums[i];

                int low = i + 1;

                int high = nums.Length - 1;

                while(low < high)

                {

                    if(nums[low] + nums[high] == newTarget)

                    {

                        var list = new List<int>(){nums[i], nums[low], nums[high]};

                        result.Add(list);

                        while(low < high && nums[low] == nums[low + 1])

                            low++;

                        while(low < high && nums[high] == nums[high - 1])

                            high--;

                        low++;

                        high--;

                    }

                    else if(nums[low] + nums[high] > newTarget)

                    {

                        high--;

                    }

                    else

                    {

                        low++;

                    }

                }

            }

        }

        return result;

    }

    private static List<List<int>> ThreeSumWithDup(int[] nums, int target)

    {

        List<List<int>> result = new List<List<int>>();

        for(int i = 0; i < nums.Length - 2; i++)

        {

            var twoSum = TwoSum(nums, target - nums[i], i);

            if(twoSum != null)

            {

                var list = new List<int>();

                list.Add(nums[i]);

                list.Add(twoSum[0]);

                list.Add(twoSum[1]);

                result.Add(list);

            }

        }

        return result;

    }

    private static int[] TwoSum(int[] nums, int target, int current)

    {

        var cache = new Dictionary<int, int>();

        for(int i = 0; i < nums.Length; i++)

        {

            if(i == current)

                continue;

            if(!cache.ContainsKey(target - nums[i]))

                cache[nums[i]] = i;

            else

                return new int[] {target - nums[i], nums[i]};

        }

        return null;

    }

    private static void Print(List<List<int>> result)

    {

        foreach(var list in result)

        {

            Console.WriteLine(string.Join(",", list.ToArray()));

        }

    }

}