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

Question

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

Answer 1

Я уверен, что есть лучший способ, но вот идея:

1. Сортировать массив
2. Для каждого элемента e в массиве двоичный поиск дополнения (sum - e)

Обе эти операции O(n log n).

Answer 2

Это можно сделать в O(n) с использованием хеш-таблицы. Инициализируйте таблицу со всеми числами в массиве, с номером в качестве ключа и частотой в качестве значения. Просмотрите все числа в массиве и посмотрите, существует ли в таблице (sum - number). Если это так, у вас есть совпадение. После того, как вы перебрали все числа в массиве, у вас должен быть список всех пар, которые суммируются до нужного числа.

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

Случай, когда n и таблица [S-n] дважды ссылаются на одно и то же число, может быть рассмотрен с дополнительной проверкой, но сложность остается O(n).

Answer 3

Использовать хеш-таблицу . Вставьте каждое число в вашу хэш-таблицу вместе с ее индексом. Тогда пусть S будет вашей желаемой суммой. Для каждого числа array[i] в вашем исходном массиве посмотрите, существует ли в вашей хеш-таблице S - array[i] с индексом, отличным от i.

Средний случай - O(n), наихудший случай - O(n^2), поэтому используйте решение для двоичного поиска, если боитесь наихудшего случая.

Answer 4

Допустим, мы хотим найти два числа в массиве A, которые при сложении вместе равны N.

1. Сортировать массив.
2. Найти наибольшее число в массиве, которое меньше N / 2. Установите индекс этого числа как ниже .
3. Инициализировать верхний , чтобы быть нижний + 1.
4. Набор сумма = A [ нижний ] + A [ верхний ].
5. Если сумма == N, готово.
6. Если сумма верхнее .
7. Если сумма > N, уменьшение ниже .
8. Если либо нижний , либо верхний находится вне массива, выполняется без каких-либо совпадений.
9. Вернитесь к 4.

Сортировка может быть выполнена в O (n log n). Поиск производится по линейному времени.

Answer 5

Это на Java: даже удаляет возможные дубликаты. Время выполнения - O(n^2)

private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;

private static void algorithm()
{
    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
    for (int i=0; i<intArray.length; i++) 
    {
        intMap.put(i, intArray[i]);
        if(intMap.containsValue(sum - intArray[i]))
            System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));

    }
    System.out.println(intMap);
}

Answer 6

def sum_in(numbers, sum_):
    """whether any two numbers from `numbers` form `sum_`."""
    a = set(numbers) # O(n)
    return any((sum_ - n) in a for n in a) # O(n)

Пример:

>>> sum_in([200, -10, -100], 100)
True

Answer 7

Вот алгоритм, который работает в O (n), если массив уже отсортирован, или O (n log n), если он еще не отсортирован. Принимает подсказки от многих других ответов здесь. Код написан на Java, но здесь псевдокод также получен из множества существующих ответов, но в целом оптимизирован для дубликатов

1. Счастливое предположение, если первый и последний элементы равны цели
2. Создать карту с текущим значением и его вхождениями
3. Создайте посещенный набор, который содержит элементы, которые мы уже видели, он оптимизирует дубликаты, например, с входом (1,1,1,1,1,1,2) и целью 4, мы вычисляем только 0 и последний элемент, а не все 1 в массиве.

4. Используйте эти переменные для вычисления существования цели в массиве; установите currentValue в массив [ith]; установить newTarget в цель - currentValue; установите для ожидаемого значения 2, если currentValue равно newTarget или 1, в противном случае

   И вернуть истину, только если а. мы никогда не видели это целое число до б. у нас есть некоторое значение для newTarget на карте, которую мы создали с. и счетчик для newTarget равен или больше ожидаемогоCount

ИНАЧЕ повторяйте шаг 4 до тех пор, пока мы не достигнем конца массива и не вернем false ИНОЕ;

Как я уже говорил, наилучшее возможное использование для посещенного магазина - когда у нас есть дубликаты, это никогда не поможет, если ни один из элементов не является дубликатом.

Java-код на https://gist.github.com/eded5dbcee737390acb4

Answer 8

Это O (n)

public static bool doesTargetExistsInList(int Target, int[] inputArray)
{
    if (inputArray != null && inputArray.Length > 0 )
    {
        Hashtable inputHashTable = new Hashtable();

        // This hash table will have all the items in the input array and how many times they appeard
        Hashtable duplicateItems = new Hashtable();

        foreach (int i in inputArray)
        {
            if (!inputHashTable.ContainsKey(i))
            {
                inputHashTable.Add(i, Target - i);
                duplicateItems.Add(i, 1);
            }
            else
            {
                duplicateItems[i] = (int)duplicateItems[i] + 1;    
            }

        }

        foreach (DictionaryEntry de in inputHashTable)
        {
            if ((int)de.Key == (int)de.Value)
            {
                if ((int)duplicateItems[de.Key] > 1)
                return true;
            }
            else if (inputHashTable.ContainsKey(de.Value))
            {
                return true;
            }
        }
    }
    return false;
}

Answer 9

Вот попытка на C. Это не помечено как домашнее задание.

// Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
   int i = 0, k = size - 1;
   int curSum;
   while(i < k)
   {
      curSum = array[i] + array[k];
      if(curSum == sum)
      {
         printf("Found match at indices %d, %d\n", i, k);
         i++;k--;
      }
      else if(curSum < sum)
      {
         i++;
      }
      else
      {
         k--;
      }
   }
}

Вот некоторые результаты теста с использованием int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };

Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..

Поиск линейный, поэтому O (n). Сортировка, которая происходит за кулисами, будет O (n * logn), если вы используете один из хороших сортов.

Из-за математики, лежащей в основе Big-O, меньший член в аддитивных терминах будет эффективно выпадать из вашего расчета, и вы получите O (n logn).

Answer 10

1. Решил вопрос в Swift 4.0
2. Решено 3 различными способами (с 2 различными типами возврата -> логическое значение и индексы)

A) TimeComplexity => 0 (n Log n) SpaceComplexity => 0 (n).

B) TimeComplexity => 0 (n ^ 2) SpaceComplexity => 0 (1).

C) TimeComplexity => 0 (n) SpaceComplexity => 0 (n)

3. Выберите решение A, B или C в зависимости от TradeOff.

   //***********************Solution A*********************//
   //This solution returns TRUE if any such two pairs exist in the array
   func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //Helper Function
   
               if end < start {
                   return -1
               } else {
                   let midIndex = (start + end) / 2
   
                   if list[midIndex] > key {
                       return binarySearch(list: list, key: key, start: start, end:  midIndex - 1)
                   } else if list[midIndex] < key {
                       return binarySearch(list: list, key: key, start: midIndex + 1, end: end)
                   } else {
                       return midIndex
                   }
               }
           }
   
           func twoPairSum(sum : Int, inputArray: [Int]) -> Bool {
   
               //Do this only if array isn't Sorted!
               let sortedArray = inputArray.sorted()
   
               for (currentIndex, value)  in sortedArray.enumerated() {
                   if let indexReturned =  binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) {
                       if indexReturned != -1 && (indexReturned != currentIndex) {
                           return true
                       }
                   }
               }
               return false
           }
   
    //***********************Solution B*********************//
    //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
    func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               for currentIndex in 0..<nums.count {
                   for nextIndex in currentIndex+1..<nums.count {
                       if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) {
                           return [currentIndex, nextIndex]
                       }
                   }
               }
   
               return []
           }
   
           func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//Helper Function
               return (firstElement + secondElement) == target
           }
   
       //*******************Solution C*********************//
      //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
      func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               var dict = [Int: Int]()
   
               for (index, value) in nums.enumerated() {
                   dict[value] = index
               }
   
               for (index, value) in nums.enumerated() {
                   let otherIndex = dict[(target - value)]
                   if otherIndex != nil && otherIndex != index {
                       return [index, otherIndex!]
                   }
               }
   
               return []
           }