Как написать алгоритм, чтобы проверить, совпадает ли сумма любых двух чисел в массиве / списке с данным числом?

Question

Как мне написать алгоритм, чтобы проверить, совпадает ли сумма любых двух чисел в массиве / списке с данным числом со сложностью nlogn?

Answer 1

    public void sumOfTwoQualToTargetSum()
    {
        List<int> list= new List<int>();
        list.Add(1);
        list.Add(3);
        list.Add(5);
        list.Add(7);
        list.Add(9);

        int targetsum = 12;

        int[] arr = list.ToArray();

        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = 0; j < arr.Length; j++)
            {
                if ((i != j) && ((arr[i] + arr[j]) == targetsum))
                {
                    Console.Write("i =" + i);
                    Console.WriteLine("j =" + j);
                }
            }
        }
    }

Answer 2

Шаг 1: сортировка массива по O (n logn)

Шаг 2: Найти два индекса

0 <= i <j <= n в [0..n], так что a [i] + a [j] == k, где k - ключ. </p>

int i=0,j=n;
while(i<j) {
   int sum = a[i]+a[j];
   if(sum == k)
        print(i,j)
   else if (sum < k)
        i++;
   else if (sum > k)
        j--;
}

Answer 3

Зависит от случая, если вам нужна только одна сумма O (N) или O (N log N) или все суммы O (N ^ 2) или O (N ^ 2 log N). В последнем случае лучше использовать БПФ>