Friday, September 11, 2020

Find a triplet in an array that sum to given value with handling of duplicates

        public IList<IList<int>> ThreeSum(int[] nums, int target)

        {

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

            Array.Sort(nums);

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

            {

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

                {

                    continue;

                }

                int low = i + 1, high = nums.Length - 1;

                while (low < high)

                {

                    if (high < nums.Length - 1 && nums[high] == nums[high + 1])

                    {

                        --high;

                        continue;

                    }

                    if (nums[low] + nums[high] + nums[i] == target)

                    {

                        result.Add(new List<int> { nums[i], nums[low], nums[high] });

                        ++low;

                        --high;

                    }

                    else if (nums[low] + nums[high] + nums[i] < target)

                    {

                        ++low;

                    }

                    else

                    {

                        --high;

                    }

                }

            }


            return result;

        }

No comments:

Post a Comment