Untitled

mail@pastecode.io avatar
unknown
csharp
a year ago
1.9 kB
2
Indexable
Never
public static IList<int> FindIndexesOfNumbers(int[] arr, int sum)
        {
            int n = arr.Length;
            // Key: Sum of pair
            // Value: List of pairs of indexes, ex: [ [0, 1], [0, 2] ]
            IDictionary<int, IList<IList<int>>> sumOfPairsAndListOfIndexes = new Dictionary<int, IList<IList<int>>>();

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    int currSum = arr[i] + arr[j];
                    
                    if(!sumOfPairsAndListOfIndexes.ContainsKey(currSum))
                    {
                        sumOfPairsAndListOfIndexes[currSum] = new List<IList<int>>();
                    }
                    sumOfPairsAndListOfIndexes[currSum].Add(new List<int>() { i, j });                  
                }
            }

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    int currSum = arr[i] + arr[j];
                    int sumOfPair = sum - currSum;
                    

                    if (sumOfPairsAndListOfIndexes.ContainsKey(sumOfPair))
                    {
                        IList<IList<int>> curr = sumOfPairsAndListOfIndexes[sumOfPair];
                        foreach (List<int> currPairOfIndexes in curr)
                        {
                            if (currPairOfIndexes[0] != i && currPairOfIndexes[1] != i
                            && currPairOfIndexes[0] != j && currPairOfIndexes[1] != j)
                            {
                                return new List<int>() { i, j, currPairOfIndexes[0], currPairOfIndexes[1] };
                            }
                        }
                    }
                }
            }

            return new List<int>();
        }