algorithm - sumar - Encuentre un par de elementos de una matriz cuya suma sea igual a un número dado

sumar elementos de un arreglo c++

Question

Dado una matriz de n enteros y dado un número X, encuentre todos los pares únicos de elementos (a, b), cuya suma es igual a X.

La siguiente es mi solución, es O (nLog (n) + n), pero no estoy seguro de si es óptima o no.

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] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

Answer 1

Acabo de asistir a esta pregunta en HackerRank y esta es mi solución ''Objective C'' :

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

        if(dict[a[i]]) {
            count++;
            NSLog(@"a[i]: %@, dict[array[i]]: %@", a[i], dict[a[i]]);
        }
        else{
            NSNumber *calcNum = @(k.longLongValue-((NSNumber*)a[i]).longLongValue);
            dict[calcNum] = a[i];
        }

    }
    return @(count);
}

Espero que ayude a alguien.

Answer 2

Aquí está el código de Java para tres enfoques:
1. Usando Map O (n), HashSet también se puede usar aquí.
2. Ordenar array y luego usar BinarySearch para buscar el complemento O (nLog (n))
3. Tradicional BruteForce dos bucles 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<Integer, Integer> pairs = new HashMap<Integer, Integer>();
        for(int i=0; i<a.length; i++){
            if(pairs.containsKey(sum-a[i]))
                System.out.println("("+a[i]+","+(sum-a[i])+")");
            else
               pairs.put(a[i], 0);
        }
    }



//Method2 - O(nlog(n)) using Sort
static void findPairs2(int[]a, int sum){
        Arrays.sort(a);
        for(int i=0; i<a.length/2; i++){
            int complement = sum - a[i];
            int foundAtIndex = Arrays.binarySearch(a,complement);
            if(foundAtIndex >0 && 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<a.length; i++){
        for(int j=i; j<a.length;j++){
            if(a[i]+a[j] == sum)
                System.out.println("("+a[i]+","+a[j]+")");
        }
    }
}

}

Answer 3

Aquí hay una solución que toma en cuenta las entradas duplicadas. Está escrito en javascript y supone que array está ordenado. La solución se ejecuta en el tiempo O (n) y no utiliza ninguna memoria adicional aparte de la variable.

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<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=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;
}

Lo resolví durante una entrevista para una gran corporación. Lo tomaron pero no yo. Entonces aquí está para todos.

Comienza en ambos lados de la matriz y avanza lentamente hacia adentro asegurándote de contar los duplicados si existen.

Solo cuenta pares, pero se puede volver a trabajar para

• encuentra los pares
• encontrar pares <x
• buscar pares> x

¡Disfrutar!

Answer 4

Buena solución de Codeaddict. Me tomé la libertad de implementar una versión en 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) solo tenemos que eliminar la instrucción && !result[sum-l]

Answer 5

C ++ 11, complejidad de tiempo de ejecución O (n):

#include <vector>
#include <unordered_map>
#include <utility>

std::vector<std::pair<int, int>> FindPairsForSum(
        const std::vector<int>& data, const int& sum)
{
    std::unordered_map<int, size_t> umap;
    std::vector<std::pair<int, int>> 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;
}

Answer 6

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

Answer 7

En 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

Answer 8

En)

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)

Metodología: a + b = c, entonces en lugar de buscar (a, b) buscamos a = c - b

Answer 9

Esto imprime los pares y evita duplicados usando la manipulación bit a bit.

public static void findSumHashMap(int[] arr, int key) {
    Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
    for(int i=0;i<arr.length;i++)
        valMap.put(arr[i], i);

    int indicesVisited = 0; 
    for(int i=0;i<arr.length;i++) {
        if(valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) {
            if(!((indicesVisited & ((1<<i) | (1<<valMap.get(key - arr[i])))) > 0)) {
                int diff = key-arr[i];
                System.out.println(arr[i] + " " +diff);
                indicesVisited = indicesVisited | (1<<i) | (1<<valMap.get(key - arr[i]));
            }
        }
    }
}

Answer 10

Hay 3 enfoques para esta solución:

Deje que la suma sea T y n sea del tamaño de la matriz

Enfoque 1:
La forma ingenua de hacer esto sería verificar todas las combinaciones (n elegir 2). Esta búsqueda exhaustiva es O (n ² ).

Enfoque 2:
Una mejor forma sería ordenar la matriz. Esto toma O (n log n)
Luego, para cada x en la matriz A, use la búsqueda binaria para buscar Tx. Esto tomará O (nlogn).
Entonces, la búsqueda general es O (n log n)

Enfoque 3:
La mejor manera sería insertar cada elemento en una tabla hash (sin clasificación). Esto toma O (n) como inserción de tiempo constante.
Luego, para cada x, podemos buscar su complemento, Tx, que es O (1).
En general, el tiempo de ejecución de este enfoque es O (n).

Puede referirse más here .Gracias.

Answer 11

Implementación de 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])

Salida:

1 + 4
2 + 3

Answer 12

Mi solución - Java - Sin duplicados

    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<Integer,Integer> 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<j){
            System.out.printf("a[%d] + a[%d] = %d + %d = %d/n",i,j,a[i],a[j],x);
        }
    }
    System.out.println("------------------------------");
}

Answer 13

Otra solución en Swift: la idea es crear un hash que almacene los valores de (sum - currentValue) y comparar esto con el valor actual del bucle. La complejidad es O (n).

func findPair(list: [Int], _ sum: Int) -> [(Int, Int)]? {
    var hash = Set<Int>() //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<Int>() //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)

Answer 14

Pasé por alto la manipulación de bits y simplemente comparé los valores de índice. Esto es menor que el valor de iteración del ciclo (i en este caso). Esto no imprimirá los pares duplicados y los elementos de matriz duplicados también.

public static void findSumHashMap(int[] arr, int key) {
    Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
    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);
            }
        }
    }
}

Answer 15

Puedo hacerlo en O (n). Avísame cuando quieras la respuesta. Tenga en cuenta que se trata simplemente de atravesar la matriz una vez sin clasificación, etc ... También debo mencionar que explota la conmutatividad de la suma y no utiliza hashes pero desperdicia memoria.

usando el sistema; utilizando System.Collections.Generic;

/ * Existe un enfoque O (n) mediante el uso de una tabla de búsqueda. El enfoque es almacenar el valor en un "contenedor" que se puede buscar fácilmente (por ejemplo, O (1)) si es un candidato para una suma apropiada.

p.ej,

para cada a [k] en la matriz, simplemente la colocamos en otra matriz en la ubicación x - a [k].

Supongamos que tenemos [0, 1, 5, 3, 6, 9, 8, 7] yx = 9

Creamos una nueva matriz,

índice de valor

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

ENTONCES los únicos valores que importan son los que tienen un índice en la nueva tabla.

Entonces, cuando lleguemos a 9, veremos si nuestra nueva matriz tiene el índice 9 - 9 = 0. Como sabemos, todos los valores que contiene se agregarán a 9. (tenga en cuenta que es obvio que solo hay 1 posible) uno pero puede tener múltiples valores de índice que debemos almacenar).

Entonces, efectivamente, lo que terminamos haciendo es solo tener que movernos a través de la matriz una vez. Debido a que la suma es conmutativa, terminaremos con todos los resultados posibles.

Por ejemplo, cuando llegamos a 6, obtenemos el índice en nuestra nueva tabla como 9 - 6 = 3. Como la tabla contiene ese valor de índice, conocemos los valores.

Esto es esencialmente cambiar la velocidad de la memoria. * /

namespace sum
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = 25;
            int X = 10;
            var arr = new List<int>();
            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<Tuple<int,int>>();
            var arrfast = new List<Tuple<int,int>>();

            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<int, int>(arr[i], arr[j]));




            int M = 500;
            var lookup = new List<List<int>>();
            for(int i = 0; i < 1000; i++) lookup.Add(new List<int>());
            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<int, int>(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();
        }
    }
}

Answer 16

Solución 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);
}

Answer 17

Solución en Python usando lista de comprensión

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

O (N ² )

también da dos pares ordenados- (a, b) y (b, a) también

Answer 18

Solución en java. Puede agregar todos los elementos de Cadena a una ArrayList de cadenas y devolver la lista. Aquí solo estoy imprimiéndolo.

void numberPairsForSum(int[] array, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    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);
    }
}

Answer 19

Un programa simple en Java para arreglos que tienen elementos únicos:

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<Integer> set = new HashSet<Integer>();    
      for(int i=0;i<input.length;i++){

        if(set.contains(input[i]))
            System.out.println(input[i] +", "+(k-input[i]));
        else
            set.add(k-input[i]);
       }
    }
}

Answer 20

Un simple fragmento de código Java para imprimir los pares siguientes:

    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<difference){
        System.out.printf("(%d, %d) %n", value, difference);
        }
    }
    }

Answer 21

Una solución puede ser esto, pero no optimul (La complejidad de este código es O (n ^ 2)):

public class FindPairsEqualToSum {

private static int inputSum = 0;

public static List<String> findPairsForSum(int[] inputArray, int sum) {
    List<String> list = new ArrayList<String>();
    List<Integer> inputList = new ArrayList<Integer>();
    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;
   }
}

Answer 22

Una versión de python simple del código que encuentra una suma de cero y se puede modificar 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

La complejidad del tiempo de ejecución de la función es O (n) y Espacio: O (n) también.

Answer 23

esta es la implementación de O (n * lg n) utilizando la implementación de búsqueda binaria dentro de un ciclo.

#include <iostream>

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

Answer 24

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

var z = (desde a en arr desde b en arr donde 10 - a == b seleccione nuevo {a, b}). ToList;

Answer 25

menos de o (n) solución será =>

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

Answer 26

https://github.com/clockzhong/findSumPairNumber

Lo hice bajo un costo de complejidad O (m + n) para el tiempo y el espacio de la memoria. Sospecho que ese es el mejor algoritmo hasta ahora.

Answer 27

Implementación en Java: utilizando el algoritmo de codaddict (Tal vez ligeramente 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<Integer, Integer> pairs = new HashMap<Integer, Integer>();

    for(int i=0;i<input.length;i++){

        if(pairs.containsKey(input[i]))
            System.out.println(input[i] +", "+ pairs.get(input[i]));
        else
            pairs.put(k-input[i], input[i]);
    }

}
}

Para input = {2,45,7,3,5,1,8,9} y si Sum es 10

Pares de salida:

3,7 
8,2
9,1

Algunas notas sobre la solución:

• Solo iteramos una vez a través de la matriz -> O (n) tiempo
• El tiempo de inserción y búsqueda en Hash es O (1).
• El tiempo total es O (n), aunque usa espacio adicional en términos de hash.

Answer 28

Implementación en Java: utilizando el algoritmo de 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(k-a[i]) != i){
            System.out.println(k-a[i]+", "+ a[i]);
        }
    }      

}

}

Salida:

81, 79
79, 81

Si quieres pares duplicados (p. Ej .: 80,80) también puedes eliminar && (Integer) mapping.get (ka [i])! = I de la condición if y estarás listo.

Answer 29

# 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

Answer 30

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