Leetcode discuss: 15. 3Sum

 March 17, 2022

Here is the link.

C# | Time complexity O(N^2) | Use HashSet<int>

March 17, 2022
Introduction
I just like to study C# code using HashSet to find the third number, and I wrote C# code and reviewed the solution.

Time complexity O(N^2) | Remove duplicate triplet
It is easy to come out the idea to remove duplicate, but the implementation is hard to figure out if in rush.

The following C# code passes online judge.

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

namespace _15_3_sum___hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            /* Example 1
            Input: nums = [-1,0,1,2,-1,-4]
            Output: [[-1,-1,2],[-1,0,1]]
            */
            var test = ThreeSum(new int[] { -1, 0, 1, 2, -1, -4 });
            Debug.Assert(string.Join(",", test[0]).CompareTo("-1,-1,2") == 0 || string.Join(",", test[0]).CompareTo("-1,0,1") == 0);
        }

        /// <summary>
        /// March 17, 2022
        /// study code
        /// https://leetcode.com/problems/3sum/discuss/7543/15-lines-C-code-o(n2)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static IList<IList<int>> ThreeSum(int[] nums)
        {
            // Four steps: 
            // 1. sort
            // 2. pick 2th
            // 3. hash find next
            // 4. skip - remove duplicate
            var result = new List<IList<int>>();

            if (nums == null || nums.Length == 0)
            {
                return result;
            }

            var length = nums.Length;
            Array.Sort(nums);

            var set = new HashSet<int>(nums);

            for (var i = 0; i < length - 2; i++)
            {
                var first = nums[i];

                // step 4: skip to remove duplicate
                if (i > 0 && first == nums[i - 1])
                {
                    continue;
                }

                for (var j = i + 1; j < length - 1; j++)
                {
                    var second = nums[j];

                    // step 4: skip to remove duplicate
                    if (j > i + 1 && second == nums[j - 1])
                    {
                        continue;
                    }

                    var target = 0 - first - second;

                    if (target > nums[j] && set.Contains(target))
                    {
                        result.Add(new[] { first, second, target });
                    }
                    else if (target == second && nums[j + 1] == target)  // hard to figure out 
                    {
                        result.Add(new[] { first, target, target });
                    }
                }
            }

            return result;
        }
    }
}