Znajdź parę elementów z tablicy, której suma jest równa podanej liczbie

Mając tablicę n liczb całkowitych i określoną liczbę X, znajdź wszystkie unikalne pary elementów (a, b), których suma jest równa X.

Oto moje rozwiązanie, jest to O (nLog (n) + n), ale nie jestem pewien, czy jest optymalne, czy nie.

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

# 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 Kth element exists and it's different then we found a pair
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

Istnieją 3 podejścia do tego rozwiązania:

Niech sumą będzie T, a n będzie rozmiarem tablicy

Podejście 1:
Naiwnym sposobem byłoby sprawdzenie wszystkich kombinacji (n wybierz 2). To wyczerpujące poszukiwanie to O (n ² ).

Podejście 2: 
 Lepszym sposobem byłoby posortowanie tablicy. To pobiera O (n log n)
Następnie dla każdego x w tablicy A użyj wyszukiwania binarnego, aby znaleźć Tx. To zajmie O (nlogn).
Zatem ogólne wyszukiwanie to O (n log n)

Podejście 3:
Najlepszym sposobem byłoby wstawienie każdego elementu do tablicy mieszającej (bez sortowania). To przyjmuje O (n) jako stałe wstawienie w czasie.
Wtedy dla każdego x możemy po prostu wyszukać jego uzupełnienie, Tx, czyli O (1).
Ogólnie czas wykonania tego podejścia wynosi O (n).

Możesz polecić więcej tutaj . Dzięki.

Implementacja w Javie: Korzystanie z algorytmu codaddict (może trochę inny)

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

}
}

Dla input = {2,45,7,3,5,1,8,9}i jeśli suma to10

Pary wyjściowe:

3,7 
8,2
9,1

Kilka uwag na temat rozwiązania:

• Iterujemy tylko raz przez tablicę -> O (n) czas
• Czas wstawiania i wyszukiwania w skrócie wynosi O (1).
• Całkowity czas to O (n), chociaż wykorzystuje dodatkową przestrzeń pod względem skrótu.

Rozwiązanie w java. Możesz dodać wszystkie elementy String do ArrayList z ciągów i zwrócić listę. Tutaj właśnie to drukuję.

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

Implementacja Pythona:

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

Wynik:

1 + 4
2 + 3

C ++ 11, złożoność czasu wykonania 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;
}

Oto rozwiązanie, które uwzględnia zduplikowane wpisy. Jest napisany w javascript i zakłada, że ​​tablica jest posortowana. Rozwiązanie działa w czasie O (n) i nie używa żadnej dodatkowej pamięci poza zmienną.

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

Rozwiązałem to podczas rozmowy kwalifikacyjnej dla dużej korporacji. Zabrali to, ale nie ja. Więc tutaj jest dla każdego.

Zacznij od obu stron tablicy i powoli idź do wewnątrz, upewniając się, że policzyłeś duplikaty, jeśli istnieją.

Liczy tylko pary, ale można je przerobić

• znajdź pary
• znajdź pary <x
• znajdź pary> x

Cieszyć się!

Na)

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, więc zamiast szukać (a, b) szukamy a = c - b

Implementacja w Javie: Korzystanie z algorytmu 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]);
        }
    }      

}

}

Wynik:

81, 79
79, 81

Jeśli chcesz zduplikować pary (np .: 80,80), po prostu usuń && (Integer) mapping.get (ka [i])! = I z warunku if i jesteś gotowy do pracy.

Właśnie uczestniczyłem w tym pytaniu na HackerRank i oto moje rozwiązanie „Cel 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);
}

Mam nadzieję, że to komuś pomoże.

jest to implementacja O (n * lg n) przy użyciu implementacji wyszukiwania binarnego wewnątrz pętli.

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

W Pythonie

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

Niezłe rozwiązanie od Codeaddict. Pozwoliłem sobie zaimplementować jego wersję w Rubim:

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

Aby umożliwić zduplikowane pary (1,5), (5,1), musimy po prostu usunąć && !result[sum-l]instrukcję

Oto kod Java dla trzech podejść:
1. Używając Map O (n), można tu również użyć HashSet.
2. Sortuj tablicę, a następnie użyj BinarySearch, aby znaleźć uzupełnienie O (nLog (n))
3. Tradycyjne BruteForce dwie pętle 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]+")");
        }
    }
}

}

Prosty program w Javie dla tablic posiadających unikalne elementy:

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

Prosty fragment kodu Java do drukowania poniższych par:

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

Inne rozwiązanie w Swift: chodzi o utworzenie skrótu przechowującego wartości (sum - currentValue) i porównanie go z bieżącą wartością pętli. Złożoność wynosi 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)

Moje rozwiązanie - Java - bez duplikatów

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

Spowoduje to wydrukowanie par i uniknięcie duplikatów przy użyciu manipulacji bitowej.

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

Ominąłem manuplację bitów i właśnie porównałem wartości indeksu. Jest to mniej niż wartość iteracji pętli (w tym przypadku i). Nie spowoduje to wydrukowania zduplikowanych par i zduplikowanych elementów tablicy.

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

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

Jednym z rozwiązań może być to, ale nie optymalne (złożoność tego kodu to 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;
   }
}

Prosta wersja kodu w Pythonie, która znajduje sumę par równą zero i może zostać zmodyfikowana, aby znaleźć 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

Złożoność funkcji w czasie wykonywania to również O (n) i Przestrzeń: O (n).

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

rozwiązanie mniejsze niż o (n) będzie =>

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

Rozwiązanie w Pythonie wykorzystujące rozumienie list

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

O (N ² )

daje również dwie uporządkowane pary - (a, b) i (b, a)

Mogę to zrobić w O (n). Daj mi znać, kiedy chcesz otrzymać odpowiedź. Zauważ, że wymaga to po prostu jednokrotnego przejścia przez tablicę bez sortowania itp ... Powinienem również wspomnieć, że wykorzystuje przemienność dodawania i nie używa skrótów, ale marnuje pamięć.

using System; using System.Collections.Generic;

/ * Podejście O (n) istnieje przy użyciu tabeli przeglądowej. Podejście polega na przechowywaniu wartości w „koszu”, który można łatwo wyszukać (np. O (1)), jeśli jest kandydatem na odpowiednią sumę.

na przykład,

dla każdego a [k] w tablicy po prostu umieszczamy to w innej tablicy w lokalizacji x - a [k].

Załóżmy, że mamy [0, 1, 5, 3, 6, 9, 8, 7] i x = 9

Tworzymy nową tablicę,

wartość indeksów

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

WTEDY jedyne wartości, które mają znaczenie, to te, które mają indeks do nowej tabeli.

Powiedzmy, że kiedy osiągniemy 9 lub równe, zobaczymy, czy nasza nowa tablica ma indeks 9 - 9 = 0. Ponieważ wiemy, że wszystkie zawarte w niej wartości dodadzą się do 9. (zauważ, że w tym przypadku jest oczywiste, że jest tylko 1 możliwy, ale może zawierać wiele wartości indeksu, które musimy przechowywać).

W efekcie to, co ostatecznie robimy, to tylko jednokrotne przejście przez tablicę. Ponieważ dodawanie jest przemienne, otrzymamy wszystkie możliwe wyniki.

Na przykład, gdy dojdziemy do 6, otrzymujemy indeks do naszej nowej tabeli jako 9 - 6 = 3. Ponieważ tabela zawiera tę wartość indeksu, znamy wartości.

Zasadniczo polega to na zamianie szybkości na pamięć. * /

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

Rozwiązanie 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);
}

https://github.com/clockzhong/findSumPairNumber

Zrobiłem to pod kosztem złożoności O (m + n) zarówno dla czasu, jak i przestrzeni pamięci. Podejrzewam, że to najlepszy jak dotąd algorytm.

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

var z = (z a w arr z b w arr, gdzie 10 - a == b wybierz nowy {a, b}).