найти пару чисел в массиве, которые добавляют к заданной сумме

Question

Вопрос. Имеется ли в этом массиве натуральных чисел несортированная пара пар целых чисел, сумма которых равна заданной сумме?

Ограничения: Это должно быть сделано в O (n) и на месте (без какого-либо внешнего хранилища, такого как массивы, хэш-карты) (вы можете использовать дополнительные переменные / указатели)

Если это невозможно, может ли быть дано доказательство для того же самого?

Answer 1

Если у вас есть отсортированный массив, вы можете найти такую ​​пару в O (n), переместив два указателя к середине

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

Сортировка может быть выполнена O (N), если у вас есть ограничение на размер чисел (или если массив уже отсортирован в первую очередь). Даже в этом случае коэффициент log n действительно мал, и я не хочу беспокоиться об этом.

доказательство:

Если есть решение (i*, j*), предположим, без ограничения общности, что i достигает i* до того, как j достигает j*. Поскольку для всех j' между j* и j мы знаем, что a[j'] > a[j*] мы можем экстраполировать это a[i] + a[j'] > a[i*] + a[j*] = target и, следовательно, что все последующие шаги алгоритма приведут к уменьшению j, пока оно не достигнет j* (или равное значение), не давая i шанса продвинуться вперед и "пропустить" решение.

Интерпретация в другом направлении аналогична.

Answer 2

Решение O(N) времени и O(1) пространства, которое работает с отсортированным массивом:

Пусть M будет значением, которое вы ищете. Используйте два указателя, X и Y. Начните X=0 в начале и Y=N-1 в конце. Вычислите сумму sum = array[X] + array[Y]. Если sum > M, то уменьшить Y, в противном случае увеличить X. Если указатели пересекаются, то решения не существует.

Вы можете выполнить сортировку на месте, чтобы получить это для общего массива, но я не уверен, что существует O(N) временное и O(1) пространственное решение в целом.

Answer 3

Как @PengOne упомянул, что это невозможно в общей схеме вещей.Но если вы наложите некоторые ограничения на данные i / p.

1. все элементы все + или все -, если нет, то нужно будет знать диапазон (максимум, минимум) и внести изменения.
2. K, сумма двух целых невелика по сравнению с элементами в целом.
3. Можно уничтожить массив i / p A [N].

Шаг 1: Переместить всеэлементы меньше чем SUM к началу массива, скажем, в N проходов мы разделили массив на [0, K] & [K, N-1], так что [0, K] содержит элементы <= SUM. </p>

Шаг 2: Поскольку мы знаем границы (от 0 до SUM), мы можем использовать сортировку по основанию.

Шаг 3: Используйте бинарный поиск по A [K], одна хорошая вещь заключается в том, что если нам нужно найти дополнительный элемент, нам нужно посмотреть только половину массива A [K].поэтому в A [k] мы перебираем A [0 - K / 2 + 1], нам нужно выполнить бинарный поиск в A [i - K].

Итак, всего ок.время N + K + K / 2 lg (K), где K - количество элементов от 0 до суммы в i / p A [N]

Примечание: если вы используете подход @ PengOne, вы можете выполнить шаг 3в К. Таким образом, общее время будет N + 2K, что определенно O (N)

Мы не используем никакой дополнительной памяти, но уничтожаем массив i / p, что также неплохо, так как у него не было никакогозаказ для начала.

Answer 4

Это может быть возможно, если массив содержит числа, верхний предел которых известен вам заранее.Затем используйте сортировку по счетам или сортировку по основанию (o (n)) и используйте алгоритм, предложенный @PengOne.

В противном случае я не могу думать о решении O (n).way: -

Сначала отсортируйте массив, используя сортировку слиянием или быструю сортировку (на месте).Найти, если в этом отсортированном массиве есть sum - array_element.Для этого можно использовать бинарный поиск.

So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).

Answer 5

Сначала отсортируйте массив, используя radix sort .Это отбросит тебя обратно (кН).Затем действуйте, как подсказывает @PengOne.

Answer 6

Следующий сайт дает простое решение, используя hashset, который видит число, а затем ищет в hashset данное текущее число http://www.dsalgo.com/UnsortedTwoSumToK.php

Answer 7

Вот алгоритм O (N). Он основан на алгоритме удаления дубликатов O (N) и наличии хорошей хеш-функции для целых чисел в вашем массиве.

Сначала удалите все дубликаты из массива.

Во-вторых, пройдите через массив и замените каждое число x на min (x, S-x), где S - сумма, которую вы хотите достичь.

В-третьих, найдите, есть ли в массиве дубликаты: если дублирован «x», то в исходном массиве должны быть «x» и «S-x», и вы нашли свою пару.

Answer 8

1. Используйте сортировку счетчика для сортировки массива O (n).

2. взять два указателя, один из которых начинается с 0-го индекса массива, а другой - с конца массива (n-1).

   запустить цикл до низкого уровня <= высокий </p>

   Sum = arr[low] + arr[high]  
   if(sum == target)
          print low, high
   if(sum < target)
          low++
   if(sum > target)
          high--
   

   Шаг 2 - 10 занимает время O (n), а сортировка при подсчете занимает O (n). Таким образом, общая сложность времени будет O (n).

Answer 9

Мое решение на Java (сложность времени O (n)), это выведет все пары с заданной суммой

import java.util.HashMap;
import java.util.Map;

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Integer, Integer> hash = new HashMap<>();
    int arr[] = {1,4,2,6,3,8,2,9};
    int sum = 5;
    for (int i = 0; i < arr.length; i++) {
        hash.put(arr[i],i);
    }

    for (int i = 0; i < arr.length; i++) {
        if(hash.containsKey(sum-arr[i])){
            System.out.println(i+ " " +  hash.get(sum-arr[i]));
        }
    }
}
}

Answer 10

В javascript: этот код, когда n больше, чем время и количество итераций увеличивается.Номер теста, выполненного программой, будет равен ((n * (n / 2) + n / 2), где n - количество элементов. Указанное количество сумм отбрасывается в if (arr [i] + arr [j] === 0) где 0 может быть любым заданным числом.

var arr = [-4, -3, 3, 4];          
                var lengtharr = arr.length;        
                var i = 0;                         
                var j = 1;                         
                var k = 1;                          
                do {                                                    
                    do {
                        if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); }
                     j++;
                    } while (j < lengtharr);        
                    k++;
                    j = k;
                    i++;
                } while (i < (lengtharr-1));