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

Ответ 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 шанс продвинуться вперед и "пропустить" решение.

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

Ответ 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).

Ответ 3

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

В противном случае Я не могу придумать решение O (n). Но решение O (nlgn) работает таким образом: -

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

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

Здесь O (N) алгоритм. Он полагается на алгоритм удаления дубликатов на месте O (N) и существование хорошей хеш-функции для int в вашем массиве.

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

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

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

Ответ 8

Мое решение в 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]));
        }
    }
}
}

Ответ 9

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

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

  запустите цикл до тех пор, пока low <= high

  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).

Ответ 10

Вот решение, которое учитывает дубликаты записей. Он написан в javascript и работает с использованием отсортированных и несортированных массивов. Решение работает в O (n) времени.

var count_pairs_unsorted = function(_arr,x) {
  // setup variables
  var asc_arr = [];
  var len = _arr.length;
  if(!x) x = 0;
  var pairs = 0;
  var i = -1;
  var k = len-1;
  if(len<2) return pairs;
  // tally all the like numbers into buckets
  while(i<k) {
    asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    i++;
    k--;
  }
  // odd amount of elements
  if(i==k) {
    asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
    k--;
  }
  // count all the pairs reducing tallies as you go
  while(i<len||k>-1){
    var y;
    if(i<len){
      y = x-_arr[i];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
        if(_arr[i]==y) {
          var comb = 1;
          while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[i]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[i]] = 0;
      }

    }
    if(k>-1) {
      y = x-_arr[k];
      if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) {
        if(_arr[k]==y) {
          var comb = 1;
          while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);}
        } else pairs+=asc_arr[_arr[k]]*asc_arr[y];
        asc_arr[y] = 0;
        asc_arr[_arr[k]] = 0;
      }

    }
    i++;
    k--;
  }
  return pairs;
}

Начните с обеих сторон массива и медленно прокладывайте себе путь внутрь, подсчитывая, сколько раз каждый номер найден. Как только вы достигнете середины, все числа будут подсчитаны, и теперь вы можете продвигать оба указателя, считая пары, когда вы идете.

Он учитывает только пары, но может быть переработан на

• найти пары
• найти пары < x
• найти пары > x

Наслаждайтесь!

Ответ 11

Реализация Ruby

ar1 = [ 32, 44, 68, 54, 65, 43, 68, 46, 68, 56]
for i in 0..ar1.length-1
 t  = 100 - ar1[i]
  if ar1.include?(t)
    s= ar1.count(t)
    if s < 2
      print   s , " - " ,  t, " , " , ar1[i]  , " pair ", i, "\n"
    end
  end
end

Ответ 12

Не гарантируется, что это возможно; как выбрана данная сумма?

Пример: несортированный массив целых чисел

2, 6, 4, 8, 12, 10

Данная сумма:

7

??

Ответ 13

Вот решение в python:

a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8,
     9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2,
     8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9,
     2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78]
i = 0
j = len(a) - 1
my_sum = 8
finded_numbers = ()
iterations = 0
while(OK):
    iterations += 1
    if (i < j):
        i += 1
    if (i == j):
        if (i == 0):
            OK = False
            break
        i = 0
        j -= 1
    if (a[i] + a[j] == my_sum):
        finded_numbers = (a[i], a[j]) 
        OK = False
print finded_numbers
print iterations

Ответ 14

Мне был задан этот же вопрос во время интервью, и это та схема, которую я имел в виду. Там осталось улучшение, чтобы разрешить отрицательные числа, но нужно было бы только изменить индексы. Пространство - это нехорошо, но я считаю, что время работы здесь будет O (N) + O (N) + O (подмножество N) → O (N). Возможно, я ошибаюсь.

void find_sum(int *array_numbers, int x){
 int i, freq, n_numbers; 
 int array_freq[x+1]= {0}; // x + 1 as there could be 0’s as well
 if(array_numbers)
 {
  n_numbers = (int) sizeof(array_numbers);
  for(i=0; i<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N) 
  for(i=0; i<n_numbers;i++) 
  { //O(N) 
   if ((array_freq[x-array_numbers[i]] > 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2)))
   { 
    freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]];
    printf("-{%d,%d} %d times\n",array_numbers[i],x-array_numbers[i],freq ); 
    // "-{3, 7} 6 times" if there’s 3 ‘7’s and 2 ‘3’s
    array_freq[array_numbers[i]]=0;
    array_freq[x-array_numbers[i]]=0; // doing this we don’t get them repeated
   }
  } // end loop
  if ((x%2)=0)
  {
   freq = array_freq[x/2];
   n_numbers=0;
   for(i=1; i<freq;i++)
   { //O([size-k subset])
    n_numbers+= (freq-i); 
   } 
   printf("-{%d,%d} %d times\n",x/2,x/2,n_numbers);
  }
  return;
 }else{
 return; // Incoming NULL array 
 printf("nothing to do here, bad pointer\n");
 }
}

Критики приветствуются.

Ответ 15

В java это зависит от максимального числа в массиве. он возвращает int [], имеющую индексы двух элементов. это O (N).

  public static int[] twoSum(final int[] nums, int target) {
    int[] r = new int[2];
    r[0] = -1;
    r[1] = -1;
    int[] vIndex = new int[0Xffff];
    for (int i = 0; i < nums.length; i++) {
        int delta = 0Xfff;
        int gapIndex = target - nums[i] + delta;
        if (vIndex[gapIndex] != 0) {
            r[0] = vIndex[gapIndex];
            r[1] = i + 1;
            return r;
        } else {
            vIndex[nums[i] + delta] = i + 1;
        }
    }
    return r;
}

Ответ 16

Сначала вы должны найти обратный массив = > сумма минус фактический массив затем проверьте, существует ли какой-либо элемент из этого нового массива в фактическом массиве.

const arr = [0, 1, 2, 6];

const sum = 8;

let isPairExist = arr
  .map(item => sum - item) // [8, 7, 6, 2];
  .find((item, index) => {
    arr.splice(0, 1); // an element should pair with another element
    return arr.find(x => x === item);
  })
  ? true : false;

console.log(isPairExist);

Ответ 17

Наивная печать двойного цикла с производительностью O (n x n) может быть улучшена до линейной производительности O (n) с использованием O (n) памяти для таблицы Hash следующим образом:

void TwoIntegersSum(int[] given, int sum)
{
    Hashtable ht = new Hashtable();
    for (int i = 0; i < given.Length; i++)
        if (ht.Contains(sum - given[i]))
            Console.WriteLine("{0} + {1}", given[i], sum - given[i]);
        else
            ht.Add(given[i], sum - given[i]);
    Console.Read();
}

Ответ 18

def pair_sum(arr,k):
    counter = 0
    lookup = set()
    for num in arr:
        if k-num in lookup:
            counter+=1
        else:
            lookup.add(num)
    return counter
    pass
pair_sum([1,3,2,2],4)

Решение в python