Leetcode discuss: 15. 3Sum

 March 17, 2022

Here is the link. 

C# | Time complexity O(N^2) | Remove duplicate by sorting, no use of HashSet<string>

March 17, 2022
Introduction
It is such great experience to learn a new approach to remove duplicate without using a HashSet. I quickly learned C# code and wrote my own practice.

Sort the array first | Compare to one side neighbor to skip duplicate
It is simple and easy to remove duplicate just by comparing to the neighbor node with same value.

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___no_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/578188/C-solution
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static IList<IList<int>> ThreeSum(int[] nums)
        {
            var result = new List<IList<int>>();
            if (nums == null || nums.Length < 3)
            {
                return result;
            }

            Array.Sort(nums);

            for (int i = 0; i < nums.Length - 2; i++)
            {
                var current = nums[i];

                // If nums[i] > 0, we can't find a valid triplet, since nums is sorted 
                // and nums[i] the smallest number.
                // To avoid duplicate triplets, we should skip nums[i] if nums[i] == nums[i-1]
                if (current > 0 || (i > 0 && current == nums[i - 1]))
                {
                    continue;
                }

                var left = i + 1;
                var right = nums.Length - 1;

                while (left < right)
                {
                    var threeSum = current + nums[left] + nums[right];

                    if (threeSum == 0)
                    {
                        result.Add(new List<int>() { nums[i], nums[left], nums[right] });
                        left++;
                        right--;

                        while (left < right && nums[left] == nums[left - 1])
                        {
                            left++;
                        }

                        while (left < right && nums[right] == nums[right + 1])
                        {
                            right--;
                        }
                    }
                    else if (threeSum > 0)
                    {
                        right--;
                    }
                    else
                    {
                        left++;
                    }
                }
            }

            return result;
        }
    }
}