[LeetCode] 3 Sum

Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Approach: We can use sorting here. Once we sort the array, We can use approach of two pointers low and high. For every nums[i], we check if there are two elements in nums[i + 1.... n] whose sum is -nums[i].

To avoid duplicate we can move i till nums[i] == nums[i + 1] and we can move high till nums[high] == nums[high - 1]. That's all!

Implementation in C#:

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

    {

        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, sumToCheck = -nums[i];

            while (low < high)

            {

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

                {

                    --high;

                    continue;

                }

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

                {

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

                    ++low;

                    --high;

                }

                else if (nums[low] + nums[high] < sumToCheck)

                {

                    ++low;

                }

                else

                {

                    --high;

                }

            }

        }

        return result;

    }

Complexity: O(n^2)