C# solution


  • 0
    A

    The Idea is to Calculate Sum of all possible pairs and store in an array of size (n*(n+1))/2. Now the problem is a modified version of Two Sum.
    '''

    public static IList<IList<int>> FourSum(int[] nums, int target)
    {
    IList<IList<int>> list = new List<IList<int>>();
    int arrayLength = nums.Length;
    Dictionary<int, List<TwoSum>> dir = new Dictionary<int, List<TwoSum>>();

            TwoSum[] coupleSum = new TwoSum[(arrayLength * (arrayLength - 1)) / 2];
            int counter = 0;
            for (int m = 0; m < arrayLength - 1; m++)
                for (int n = m + 1; n < arrayLength; n++)
                {
                    coupleSum[counter] = new TwoSum() { first = m, second = n, sum = nums[m] + nums[n] };
                    counter++;
                }
    
            for (int i = 0; i < coupleSum.Count(); i++)
            {
                if (dir.ContainsKey(target - coupleSum[i].sum))
                    NotOverlapping(coupleSum[i], dir[target - coupleSum[i].sum], list, nums);
    
                if (dir.ContainsKey(coupleSum[i].sum))
                    dir[coupleSum[i].sum].Add(coupleSum[i]);
                else
                    dir[coupleSum[i].sum] = new List<TwoSum>() { coupleSum[i] };
            }
            return list;
        }
    
        private static bool IsDuplicate(int[] nums, IList<IList<int>> list, TwoSum twoSum1, TwoSum twoSum2)
        {
            List<int> temp = new List<int>() { nums[twoSum1.first], nums[twoSum1.second], nums[twoSum2.first], nums[twoSum2.second] };
            temp.Sort();
    
            foreach (List<int> i in list)
                if (i[0].Equals(temp[0]) && i[1].Equals(temp[1]) && i[2].Equals(temp[2]) && i[3].Equals(temp[3]))
                    return true;
            return false;
        }
    
        private static void NotOverlapping(TwoSum twoSum1, List<TwoSum> listTwoSum2, IList<IList<int>> list, int[] nums)
        {
            List<TwoSum> lst = new List<TwoSum>();
            foreach (TwoSum twoSum2 in listTwoSum2)
            {
                if (twoSum1.first != twoSum2.first
                    && twoSum1.second != twoSum2.first
                    && twoSum1.first != twoSum2.second
                    && twoSum1.second != twoSum2.second
                    && !IsDuplicate(nums, list, twoSum1, twoSum2)
                    )
                {
                    List<int> temp = new List<int>() { nums[twoSum1.first], nums[twoSum1.second], nums[twoSum2.first], nums[twoSum2.second] };
                    temp.Sort();
                    list.Add(temp);
                }
            }
        }
    }
    internal class TwoSum
    {
        internal int first { set; get; }
        internal int second { set; get; }
        internal int sum { set; get; }
    }
    

    }
    ''''


Log in to reply
 

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