Znajdź parę liczb w tablicy, które dodają do podanej sumy

Rozwiązanie O(N) czasu i O(1) przestrzeni, które działa na posortowanej tablicy:

Niech M będzie wartością, której szukasz. Użyj dwóch wskaźników, X i Y. Początek X=0 na początku i Y=N-1 na końcu. Oblicz sumę sum = array[X] + array[Y]. If sum > M, then decrement Y, otherwise increment X. Jeśli wskaźniki się krzyżują, to nie ma rozwiązania.

Można sortować w miejscu, aby uzyskać to dla ogólnej tablicy, ale nie jestem pewien, czy istnieje O(N) Czas i O(1) rozwiązanie przestrzeni w ogóle.

Może to być możliwe, jeśli tablica zawiera liczby, których górna granica jest znana wcześniej. Następnie użyj sortowania liczenia lub sortowania radix (o (n)) i użyj algorytmu, który zasugerował @PengOne.

Inaczej Nie mogę wymyślić rozwiązania O (n).Ale rozwiązanie O (nlgn) działa w ten sposób:-

Najpierw posortuj tablicę używając sortowania scalającego lub szybkiego sortowania (dla inplace). Znajdź, czy sum-array_element znajduje się w tej posortowanej tablicy. Można do tego użyć wyszukiwania binarnego.

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

Jak wspomniał @PengOne nie jest to możliwe w ogólnym schemacie rzeczy. Ale jeśli wprowadzisz pewne ograniczenia dotyczące danych i / P.

1. wszystkie elementy są all + lub all -, jeśli nie, to musi znać zakres (wysoki, niski) i dokonać zmian.
2. K, suma dwóch liczb całkowitych jest rzadka w porównaniu do elementów w ogóle.
3. można zniszczyć i/P array A [N].

Krok 1: Przenieś wszystkie elementy mniejsze od sumy na początek tablicy, powiedzmy w N przedziałach mamy podzieloną tablicę na [0, K] & [K, N-1] taki, że [0, K] zawiera elementy

Krok 2: ponieważ znamy granice (od 0 do sumy) możemy użyć sortowania radix.

Krok 3: Użyj wyszukiwania binarnego na [K], dobrą rzeczą jest to, że jeśli musimy znaleźć element uzupełniający, musimy szukać tylko połowy tablicy A [K]. tak więc w[k] iterujemy przez[ 0 do K/2 + 1] musimy wykonać wyszukiwanie binarne w[I do K].

So total appx. czas jest, N + K + K / 2 lg (K) gdzie K jest liczbą elementów btw 0 do sumy w i/p A [N]

Uwaga: jeśli używasz @ PengOne ' s podejście można zrobić krok3 w K. więc całkowity czas będzie N+2K co jest zdecydowanie O (N)

Nie używamy żadnej dodatkowej pamięci, ale niszczymy tablicę i / p, która również nie jest zła, ponieważ nie miała żadnych rozkazów.

Najpierw posortuj tablicę używając Radix sort . To cię przywróci O (kN). Następnie postępuj zgodnie z sugestią @ PengOne.

Następująca strona daje proste rozwiązanie za pomocą hashset, który widzi liczbę, a następnie przeszukuje hashset dla podanej sumy-bieżącej liczby http://www.dsalgo.com/UnsortedTwoSumToK.php

Oto algorytm O(N). Opiera się ona na wbudowanym algorytmie usuwania duplikatów O(N) i istnieniu dobrej funkcji skrótu dla ints w tablicy.

Najpierw usuń wszystkie duplikaty z tablicy.

Po drugie, przejdź przez tablicę i zamień każdą liczbę x Na min (x, S-x), gdzie S jest sumą, którą chcesz osiągnąć.

Po trzecie, Znajdź duplikaty w tablicy: jeśli 'x' jest duplikowany, to 'x' i 'S-x'muszą wystąpić w oryginalnej tablicy, i znalazłeś swoją parę.

Moje rozwiązanie w Javie (złożoność czasowa O (n)), to wyświetli wszystkie pary o danej sumie

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]));
        }
    }
}
}

1. Użyj count sort do sortowania tablicy O (n).

2. Weź dwa wskaźniki jeden zaczyna się od 0 indeksu tablicy, a drugi od końca tablicy say (n-1).

   Uruchom pętlę, aż low

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

   Krok 2 do 10 zajmuje O (N) czas, a liczenie sortowania zajmuje O (n). Więc całkowita złożoność czasu będzie O (n).

Oto rozwiązanie uwzględniające zduplikowane wpisy. Jest napisany w javascript i działa przy użyciu sortowanych i niesortowanych tablic. Rozwiązanie działa w czasie 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;
}

Zacznij od obu stron tablicy i powoli idź do środka, zachowując liczbę, ile razy każda liczba została znaleziona. Po osiągnięciu punktu środkowego wszystkie liczby są zliczane i można teraz rozwijać oba wskaźniki licząc pary, jak idziesz.

Liczy tylko pary, ale można je przerobić do

• Znajdź pary
• Znajdź pary
• Znajdź pary > x

Implementacja 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

W javascript: ten kod, gdy n jest większe, to czas i liczba iteracji wzrasta. Liczba testów wykonanych przez program będzie równa ((n*(n/2)+n / 2), gdzie n to liczba elementów.Podana suma liczb jest odrzucana w if (arr [i] + arr [j] = = = 0), gdzie 0 może być dowolną liczbą.

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

Nie ma gwarancji, że będzie to możliwe; w jaki sposób wybrana jest dana suma?

Przykład: nieposortowana tablica liczb całkowitych

2, 6, 4, 8, 12, 10

Podana suma:

7

??

Oto rozwiązanie w Pythonie:

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

To samo pytanie zadano mi podczas wywiadu i taki plan miałem na myśli. Jest jeszcze poprawa, aby umożliwić liczby ujemne, ale konieczna byłaby tylko modyfikacja indeksów. Spacja nie jest dobra, ale uważam, że czas pracy Tutaj byłby O (N)+O(N)+O (podzbiór N) -> O (N). Mogę się mylić.

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”);
 }
}

W Javie jest to zależne od maksymalnej liczby w tablicy. zwraca int [] o indeksach dwóch elementów. jest 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;
}

Najpierw powinieneś znaleźć odwrotną tablicę = > suma minus rzeczywista tablica następnie sprawdź, czy jakikolwiek element z nowej tablicy istnieje w rzeczywistej tablicy.

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

Naïve double loop printout with O(N x N) performance can be improved to linear O (N) performance using O (N) memory for Hash Table as following:

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();
}

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)

Rozwiązanie w Pythonie