using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        int[] arr = {0, -1, 2, -3, 1};

        //int[] arr = {1, -2, 1, 0, 5};

        ThreeSum(arr);

    }

    // this has O(n^2) time complexity due to 2 for loops and O(n) space complexity due to hashset

    // the only thing we can improve is the space complexit by reducing it to O(1) 

    // you do this by sorting all the numbers first.. and then have 2 pointers from opposite directions (left and right)

    // increment left if sum < 0 and decrement right if sum > 0; if sum = 0, move both pointers

    public static void ThreeSum(int[] arr)

    {

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

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

            for (int j = i + 1; j < arr.Length; j++) {

                var key = arr[j] * -1;

                if (dict.ContainsKey(key)) {

                    var k = dict[key];

                    Console.WriteLine($"[{arr[i]}, {arr[k]}, {arr[j]}]");

                }

                dict.Add(arr[i] + arr[j], j);

            }

        }

        Console.WriteLine("3sum");

    }

}