3Sum solution in C# with O(n*n) complexity


  • 0
    J

    public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
    Array.Sort(nums);
    IList<IList<int>> list = new List<IList<int>>();

        for (int pos = 0; pos < nums.Length - 2; pos++)
        { 
            int lo = pos+1, hi = nums.Length - 1;
            while (lo < hi)
            {
                int sum = nums[pos] + nums[lo] + nums[hi];
                if (sum == 0)
                {
                    list.Add(new List<int>{nums[pos], nums[lo], nums[hi]});
                    while (pos < nums.Length - 2 && nums[pos] == nums[pos+1]) {pos++;} 
                    while (lo < hi && nums[lo] == nums[lo+1]) {lo++;}
                    while (lo < hi && nums[hi] == nums[hi-1]) {hi--;}
                    lo++;
                    hi--;
                }
                else if (sum < 0)
                {
                    lo++;
                }
                else
                {
                    hi--;
                }
            }
        }
        return list;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.