Encontre um par de elementos de uma matriz cuja sum é igual a um determinado número

Dado array de n inteiros e dado um número X, encontre todos os pares únicos de elementos (a, b), cujo sumtório é igual a X.

O seguinte é a minha solução, é O (nLog (n) + n), mas não tenho certeza se é ou não ideal.

int main(void) { int arr [10] = {1,2,3,4,5,6,7,8,9,0}; findpair(arr, 10, 7); } void findpair(int arr[], int len, int sum) { std::sort(arr, arr+len); int i = 0; int j = len -1; while( i < j){ while((arr[i] + arr[j]) <= sum && i < j) { if((arr[i] + arr[j]) == sum) cout << "(" << arr[i] << "," << arr[j] << ")" <= sum && i < j) { if((arr[i] + arr[j]) == sum) cout << "(" << arr[i] << "," << arr[j] << ")" << endl; j--; } } } 

 # Let arr be the given array. # And K be the give sum for i=0 to arr.length - 1 do hash(arr[i]) = i // key is the element and value is its index. end-for for i=0 to arr.length - 1 do if hash(K - arr[i]) != i // if K - ele exists and is different we found a pair print "pair i , hash(K - arr[i]) has sum K" end-if end-for 

Existem 3 abordagens para esta solução:

Deixe a sum ser T e n seja o tamanho da matriz

Abordagem 1:
A maneira ingênua de fazer isso seria verificar todas as combinações (n escolher 2). Essa busca exaustiva é O (n 2 ).

Abordagem 2:
Uma maneira melhor seria classificar o array. Isso leva O (n log n)
Então, para cada x na matriz A, use a pesquisa binária para procurar por Tx. Isso levará O (nlogn).
Então, a pesquisa geral é O (n log n)

Abordagem 3:
A melhor maneira seria inserir todos os elementos em uma tabela de hash (sem sorting). Isso leva O (n) como inserção de tempo constante.
Então, para cada x, podemos apenas procurar seu complemento, Tx, que é O (1).
No geral, o tempo de execução dessa abordagem é O (n).

Você pode se referir mais aqui .

Implementação em Java: Usando o algoritmo do codaddict (talvez um pouco diferente)

 import java.util.HashMap; public class ArrayPairSum { public static void main(String[] args) { int []a = {2,45,7,3,5,1,8,9}; printSumPairs(a,10); } public static void printSumPairs(int []input, int k){ Map pairs = new HashMap(); for(int i=0;i 

Para input = {2,45,7,3,5,1,8,9} e se a sum for 10

Pares de saída:

 3,7 8,2 9,1 

Algumas notas sobre a solução:

  • Nós iteramos apenas uma vez através do array -> O (n) time
  • Inserção e tempo de pesquisa em Hash é O (1).
  • O tempo total é O (n), embora use espaço extra em termos de hash.

Solução em java Você pode adicionar todos os elementos String a uma ArrayList de strings e retornar a lista. Aqui estou apenas imprimindo.

 void numberPairsForSum(int[] array, int sum) { HashSet set = new HashSet(); for (int num : array) { if (set.contains(sum - num)) { String s = num + ", " + (sum - num) + " add up to " + sum; System.out.println(s); } set.add(num); } } 

C ++ 11, complexidade do tempo de execução O (n):

 #include  #include  #include  std::vector> FindPairsForSum( const std::vector& data, const int& sum) { std::unordered_map umap; std::vector> result; for (size_t i = 0; i < data.size(); ++i) { if (0 < umap.count(sum - data[i])) { size_t j = umap[sum - data[i]]; result.push_back({data[i], data[j]}); } else { umap[data[i]] = i; } } return result; } 

Aqui está uma solução que leva em consideração inputs duplicadas. Está escrito em javascript e assume que o array está ordenado. A solução é executada no tempo O (n) e não usa memory extra além da variável.

 var count_pairs = function(_arr,x) { if(!x) x = 0; var pairs = 0; var i = 0; var k = _arr.length-1; if((k+1)<2) return pairs; var halfX = x/2; while(i=i) pairs+=(comb++); break; } // count pair and k duplicates pairsThisLoop++; while(_arr[--k]==curK) pairsThisLoop++; // add k side pairs to running total for every i side pair found pairs+=pairsThisLoop; while(_arr[++i]==curI) pairs+=pairsThisLoop; } else { // if we are at a mid point if(curK==curI) break; var distK = Math.abs(halfX-curK); var distI = Math.abs(halfX-curI); if(distI > distK) while(_arr[++i]==curI); else while(_arr[--k]==curK); } } return pairs; } 

Eu resolvi isso durante uma entrevista para uma grande corporação. Eles levaram, mas não eu. Então, aqui é para todos.

Comece em ambos os lados da matriz e lentamente trabalhe seu caminho para dentro, certificando-se de contar as duplicatas, se existirem.

Só conta pares mas pode ser retrabalhado para

  • encontrar os pares
  • encontrar pares
  • encontrar pares> x

Apreciar!

Implementação Python:

 import itertools list = [1, 1, 2, 3, 4, 5,] uniquelist = set(list) targetsum = 5 for n in itertools.combinations(uniquelist, 2): if n[0] + n[1] == targetsum: print str(n[0]) + " + " + str(n[1]) 

Saída:

 1 + 4 2 + 3 

Em)

 def find_pairs(L,sum): s = set(L) edgeCase = sum/2 if L.count(edgeCase) ==2: print edgeCase, edgeCase s.remove(edgeCase) for i in s: diff = sum-i if diff in s: print i, diff L = [2,45,7,3,5,1,8,9] sum = 10 find_pairs(L,sum) 

Metodologia: a + b = c, então ao invés de procurar por (a, b), procuramos a = c – b

Acabei de assistir a esta pergunta no HackerRank e aqui está a minha solução ‘Objective C’ :

 -(NSNumber*)sum:(NSArray*) a andK:(NSNumber*)k { NSMutableDictionary *dict = [NSMutableDictionary dictionary]; long long count = 0; for(long i=0;i 

Espero que ajude alguém.

esta é a implementação de O (n * lg n) usando implementação de busca binária dentro de um loop.

 #include  using namespace std; bool *inMemory; int pairSum(int arr[], int n, int k) { int count = 0; if(n==0) return count; for (int i = 0; i < n; ++i) { int start = 0; int end = n-1; while(start <= end) { int mid = start + (end-start)/2; if(i == mid) break; else if((arr[i] + arr[mid]) == k && !inMemory[i] && !inMemory[mid]) { count++; inMemory[i] = true; inMemory[mid] = true; } else if(arr[i] + arr[mid] >= k) { end = mid-1; } else start = mid+1; } } return count; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; inMemory = new bool[10]; for (int i = 0; i < 10; ++i) { inMemory[i] = false; } cout << pairSum(arr, 10, 11) << endl; return 0; } 

Em python

 arr = [1, 2, 4, 6, 10] diff_hash = {} expected_sum = 3 for i in arr: if diff_hash.has_key(i): print i, diff_hash[i] key = expected_sum - i diff_hash[key] = i 

Boa solução da Codeaddict. Tomei a liberdade de implementar uma versão dele em Ruby:

 def find_sum(arr,sum) result ={} h = Hash[arr.map {|i| [i,i]}] arr.each { |l| result[l] = sum-l if h[sum-l] && !result[sum-l] } result end 

Para permitir pares duplicados (1,5), (5,1), basta remover a instrução && !result[sum-l]

Aqui está o código Java para três abordagens:
1. Usando o Mapa O (n), o HashSet também pode ser usado aqui.
2. Classifique o array e use o BinarySearch para procurar pelo complemento O (nLog (n))
3. BruteForce Tradicional dois loops O (n ^ 2)

 public class PairsEqualToSum { public static void main(String[] args) { int a[] = {1,10,5,8,2,12,6,4}; findPairs1(a,10); findPairs2(a,10); findPairs3(a,10); } //Method1 - O(N) use a Map to insert values as keys & check for number's complement in map static void findPairs1(int[]a, int sum){ Map pairs = new HashMap(); for(int i=0; i0 && foundAtIndex != i) //to avoid situation where binarySearch would find the original and not the complement like "5" System.out.println("("+a[i]+","+(sum-a[i])+")"); } } //Method 3 - Brute Force O(n^2) static void findPairs3(int[]a, int sum){ for(int i=0; i 

Um programa simples em java para matrizes com elementos exclusivos:

 import java.util.*; public class ArrayPairSum { public static void main(String[] args) { int []a = {2,4,7,3,5,1,8,9,5}; sumPairs(a,10); } public static void sumPairs(int []input, int k){ Set set = new HashSet(); for(int i=0;i 

Um trecho de código Java simples para imprimir os pares abaixo:

  public static void count_all_pairs_with_given_sum(int arr[], int S){ if(arr.length < 2){ return; } HashSet values = new HashSet(arr.length); for(int value : arr)values.add(value); for(int value : arr){ int difference = S - value; if(values.contains(difference) && value 

Outra solução no Swift: a idéia é criar um hash que armazene valores de (sum – currentValue) e compare isso com o valor atual do loop. A complexidade é O (n).

 func findPair(list: [Int], _ sum: Int) -> [(Int, Int)]? { var hash = Set() //save list of value of sum - item. var dictCount = [Int: Int]() //to avoid the case A*2 = sum where we have only one A in the array var foundKeys = Set() //to avoid duplicated pair in the result. var result = [(Int, Int)]() //this is for the result. for item in list { //keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5) if (!dictCount.keys.contains(item)) { dictCount[item] = 1 } else { dictCount[item] = dictCount[item]! + 1 } //if my hash does not contain the (sum - item) value -> insert to hash. if !hash.contains(sum-item) { hash.insert(sum-item) } //check if current item is the same as another hash value or not, if yes, return the tuple. if hash.contains(item) && (dictCount[item] > 1 || sum != item*2) // check if we have item*2 = sum or not. { if !foundKeys.contains(item) && !foundKeys.contains(sum-item) { foundKeys.insert(item) //add to found items in order to not to add duplicated pair. result.append((item, sum-item)) } } } return result } //test: let a = findPair([2,3,5,4,1,7,6,8,9,5,3,3,3,3,3,3,3,3,3], 14) //will return (8,6) and (9,5) 

Implementação em Java: Usando o algoritmo do codaddict:

 import java.util.Hashtable; public class Range { public static void main(String[] args) { // TODO Auto-generated method stub Hashtable mapping = new Hashtable(); int a[]= {80,79,82,81,84,83,85}; int k = 160; for (int i=0; i < a.length; i++){ mapping.put(a[i], i); } for (int i=0; i < a.length; i++){ if (mapping.containsKey(k - a[i]) && (Integer)mapping.get(ka[i]) != i){ System.out.println(ka[i]+", "+ a[i]); } } } } 

Saída:

 81, 79 79, 81 

Se você quer pares duplicados (por exemplo: 80,80), então apenas remova o && (Integer) mapping.get (ka [i])! = I da condição if e você está pronto para ir.

Isso imprime os pares e evita duplicatas usando manipulação bit a bit.

 public static void findSumHashMap(int[] arr, int key) { Map valMap = new HashMap(); for(int i=0;i 0)) { int diff = key-arr[i]; System.out.println(arr[i] + " " +diff); indicesVisited = indicesVisited | (1<  

Eu contornei a manipulação de bits e apenas comparei os valores do índice. Isso é menor que o valor de iteração do loop (i neste caso). Isso não imprimirá os pares duplicados e os elementos duplicados da matriz também.

 public static void findSumHashMap(int[] arr, int key) { Map valMap = new HashMap(); for (int i = 0; i < arr.length; i++) { valMap.put(arr[i], i); } for (int i = 0; i < arr.length; i++) { if (valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) { if (valMap.get(key - arr[i]) < i) { int diff = key - arr[i]; System.out.println(arr[i] + " " + diff); } } } } 

em c #:

  int[] array = new int[] { 1, 5, 7, 2, 9, 8, 4, 3, 6 }; // given array int sum = 10; // given sum for (int i = 0; i < = array.Count() - 1; i++) if (array.Contains(sum - array[i])) Console.WriteLine("{0}, {1}", array[i], sum - array[i]); 

Uma solução pode ser isso, mas não otimizada (a complexidade desse código é O (n ^ 2)):

 public class FindPairsEqualToSum { private static int inputSum = 0; public static List findPairsForSum(int[] inputArray, int sum) { List list = new ArrayList(); List inputList = new ArrayList(); for (int i : inputArray) { inputList.add(i); } for (int i : inputArray) { int tempInt = sum - i; if (inputList.contains(tempInt)) { String pair = String.valueOf(i + ", " + tempInt); list.add(pair); } } return list; } } 

Uma versão simples em python do código que encontra um par de zero e pode ser modificado para encontrar k:

 def sumToK(lst): k = 0 # < - define the k here d = {} # build a dictionary # build the hashmap key = val of lst, value = i for index, val in enumerate(lst): d[val] = index # find the key; if a key is in the dict, and not the same index as the current key for i, val in enumerate(lst): if (k-val) in d and d[k-val] != i: return True return False 

A complexidade do tempo de execução da function é O (n) e Space: O (n) também.

  public static int[] f (final int[] nums, int target) { int[] r = new int[2]; r[0] = -1; r[1] = -1; int[] vIndex = new int[0Xfff]; for (int i = 0; i < nums.length; i++) { int delta = 0Xff; 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; } 

https://github.com/clockzhong/findSumPairNumber

Eu fiz isso sob o custo de complexidade O (m + n) para o tempo e espaço de memory. Eu suspeito que esse é o melhor algoritmo até agora.

menos que o (n) solução será =>

 function(array,k) var map = {}; for element in array map(element) = true; if(map(k-element)) return {k,element} 

Minha solução – Java – sem duplicatas

  public static void printAllPairSum(int[] a, int x){ System.out.printf("printAllPairSum(%s,%d)\n", Arrays.toString(a),x); if(a==null||a.length==0){ return; } int length = a.length; Map reverseMapOfArray = new HashMap<>(length,1.0f); for (int i = 0; i < length; i++) { reverseMapOfArray.put(a[i], i); } for (int i = 0; i < length; i++) { Integer j = reverseMapOfArray.get(x - a[i]); if(j!=null && i 

Solução em Python usando a compreensão da lista

 f= [[i,j] for i in list for j in list if j+i==X]; 

O (N 2 )

também dá dois pares ordenados – (a, b) e (b, a) também

Eu posso fazer isso em O (n). Me avise quando quiser a resposta. Note que envolve simplesmente atravessar o array uma vez sem sorting, etc … Devo mencionar também que ele explora a comutatividade de adição e não usa hashes, mas desperdiça memory.


usando o sistema; using System.Collections.Generic;

/ * Uma abordagem O (n) existe usando uma tabela de pesquisa. A abordagem é armazenar o valor em um “bin” que pode ser facilmente consultado (por exemplo, O (1)) se for um candidato para uma sum apropriada.

por exemplo,

para cada um [k] na matriz nós simplesmente o colocamos em outra matriz na localização x – a [k].

Suponha que tenhamos [0, 1, 5, 3, 6, 9, 8, 7] e x = 9

Nós criamos uma nova matriz,

valor de índices

 9 - 0 = 9 0 9 - 1 = 8 1 9 - 5 = 4 5 9 - 3 = 6 3 9 - 6 = 3 6 9 - 9 = 0 9 9 - 8 = 1 8 9 - 7 = 2 7 

ENTÃO os únicos valores que importam são aqueles que têm um índice na nova tabela.

Então, digamos que quando chegarmos a 9, veremos se nossa nova matriz tem o índice 9 – 9 = 0. Já que sabemos que todos os valores que ela contém serão adicionados a 9. (note que é óbvio que há apenas 1 possível um, mas pode ter vários valores de índice nele que precisamos armazenar).

Então, efetivamente, o que acabamos fazendo é apenas ter que percorrer a matriz uma vez. Como a adição é comutativa, acabaremos com todos os resultados possíveis.

Por exemplo, quando chegarmos a 6, obtemos o índice em nossa nova tabela como 9 – 6 = 3. Como a tabela contém esse valor de índice, sabemos os valores.

Isso é essencialmente trocado pela velocidade da memory. * /

 namespace sum { class Program { static void Main(string[] args) { int num = 25; int X = 10; var arr = new List(); for(int i = 0; i < num; i++) arr.Add((new Random((int)(DateTime.Now.Ticks + i*num))).Next(0, num*2)); Console.Write("["); for (int i = 0; i < num - 1; i++) Console.Write(arr[i] + ", "); Console.WriteLine(arr[arr.Count-1] + "] - " + X); var arrbrute = new List>(); var arrfast = new List>(); for(int i = 0; i < num; i++) for(int j = i+1; j < num; j++) if (arr[i] + arr[j] == X) arrbrute.Add(new Tuple(arr[i], arr[j])); int M = 500; var lookup = new List>(); for(int i = 0; i < 1000; i++) lookup.Add(new List()); for(int i = 0; i < num; i++) { // Check and see if we have any "matches" if (lookup[M + X - arr[i]].Count != 0) { foreach(var j in lookup[M + X - arr[i]]) arrfast.Add(new Tuple(arr[i], arr[j])); } lookup[M + arr[i]].Add(i); } for(int i = 0; i < arrbrute.Count; i++) Console.WriteLine(arrbrute[i].Item1 + " + " + arrbrute[i].Item2 + " = " + X); Console.WriteLine("---------"); for(int i = 0; i < arrfast.Count; i++) Console.WriteLine(arrfast[i].Item1 + " + " + arrfast[i].Item2 + " = " + X); Console.ReadKey(); } } } 

Solução de Javascript:

 var sample_input = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]; var result = getNumbersOf(100, sample_input, true, []); function getNumbersOf(targetNum, numbers, unique, res) { var number = numbers.shift(); if (!numbers.length) { return res; } for (var i = 0; i < numbers.length; i++) { if ((number + numbers[i]) === targetNum) { var result = [number, numbers[i]]; if (unique) { if (JSON.stringify(res).indexOf(JSON.stringify(result)) < 0) { res.push(result); } } else { res.push(result); } numbers.splice(numbers.indexOf(numbers[i]), 1); break; } } return getNumbersOf(targetNum, numbers, unique, res); } 

int [] arr = {1,2,3,4,5,6,7,8,9,0};

var z = (de um in arr de b in arr onde 10 – a == b seleciona new {a, b}). ToList;