My O(n^3) two points solution


  • 0
    L

    My O(n^3) two points solution

    public class Solution
    {

        public IList<IList<int>> FourSum(int[] nums, int target)
        {
            IList<IList<int>> result = new List<IList<int>>();
    
            int len = nums.Length;
    
            for (int i = 0; i < len; i++)
            {
                for (int j = i+1; j < len; j++)
                {
                    if (nums[i] > nums[j])
                    {
                        int t = nums[i];
                        nums[i] = nums[j];
                        nums[j] = t;
                    }
                }
            }
    
    
            for (int i = 0; i <= len - 4; i++)
            {
                if (i > 0 && nums[i] == nums[i - 1])
                {
                    continue;
                }
    
                
                for (int j = i + 1; j <= len - 3; j++)
                {
                    int sum = nums[i] + nums[j];
    
                    if (j > i + 1 && nums[j] == nums[j - 1])
                    {
                        continue;
                    }
    
                    int low = j + 1;
                    int high = len - 1;
    
                    while (low < high)
                    {
                        if (sum + nums[low] + nums[high] == target)
                        {
                            result.Add(new List<int>() { nums[i], nums[j], nums[low], nums[high] });
    
                            while (low < high && nums[low] == nums[low + 1])
                            {
                                low++;
                            }
    
                            while (low < high && nums[high] == nums[high - 1])
                            {
                                high--;
                            }
    
                            low++;
                            high--;
                        }
                        else if (sum + nums[low] + nums[high] > target)
                        {
                            high--;
                        }
                        else
                        {
                            low++;
                        }
                    }
    
                }
            }
    
            return result;
    
        }
    }

Log in to reply
 

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