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

Дан массив из n целых чисел и задано число X. Найдите все уникальные пары элементов (a, b), сумма которых равна X.

Следующее - мое решение, это O (nLog (n) + n), но я не уверен, оптимально оно или нет.

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

Есть 3 подхода к этому решению:

пусть сумма равна T, а n - размер массива.

Подход 1.
Наивный способ сделать это - проверить все комбинации (n выберите 2). Этот исчерпывающий поиск составляет O (n ² ).

Подход 2: 
 лучший способ - отсортировать массив. Это занимает O (n log n).
Затем для каждого x в массиве A используйте двоичный поиск для поиска Tx. Это займет O (nlogn).
Итак, общий поиск - O (n log n).

Подход 3.
Лучшим способом было бы вставить каждый элемент в хеш-таблицу (без сортировки). Это занимает O (n) как постоянную вставку времени.
Затем для каждого x мы можем просто найти его дополнение Tx, которое равно O (1).
В целом время выполнения этого подхода составляет O (n).

Вы можете сослаться на больше здесь. Спасибо.

Реализация на Java: использование алгоритма codaddict (возможно, немного отличается)

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

}
}

Для input = {2,45,7,3,5,1,8,9}и если Sum10

Выходные пары:

3,7 
8,2
9,1

Некоторые примечания к решению:

• Мы повторяем только один раз по массиву -> O (n) раз
• Время вставки и поиска в Hash равно O (1).
• Общее время O (n), хотя для хеширования используется дополнительное пространство.

Решение в java. Вы можете добавить все элементы String в ArrayList строк и вернуть список. Вот распечатываю.

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

Реализация 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])

Вывод:

1 + 4
2 + 3

C ++ 11, сложность времени выполнения 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;
}

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

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

Я решил это во время интервью для крупной корпорации. Забрали, но не меня. Итак, вот оно для всех.

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

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

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

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

На)

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)

Методология: a + b = c, поэтому вместо поиска (a, b) мы ищем a = c - b

Реализация на Java: Использование алгоритма 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]);
        }
    }      

}

}

Вывод:

81, 79
79, 81

Если вам нужны повторяющиеся пары (например: 80,80), просто удалите && (Integer) mapping.get (ka [i])! = I из условия if, и все готово.

Только что посетил этот вопрос на HackerRank, и вот мое решение для цели 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);
}

Надеюсь, это кому-то поможет.

это реализация O (n * lg n) с использованием реализации двоичного поиска внутри цикла.

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

В питоне

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

Хорошее решение от Codeaddict. Я взял на себя смелость реализовать его версию на 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

Чтобы разрешить дублирование пар (1,5), (5,1), нам просто нужно удалить && !result[sum-l]инструкцию

Вот код Java для трех подходов:
1. Используя Map O (n), здесь также можно использовать HashSet.
2. Отсортируйте массив, а затем используйте BinarySearch для поиска дополнения O (nLog (n))
3. Традиционный двойной цикл BruteForce 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]+")");
        }
    }
}

}

Простая программа на java для массивов с уникальными элементами:

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

Простой фрагмент кода Java для печати пар ниже:

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

Другое решение в Swift: идея состоит в том, чтобы создать хэш, в котором хранятся значения (sum - currentValue), и сравнивать их с текущим значением цикла. Сложность - 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)

Мое решение - Java - без дубликатов

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

Это печатает пары и избегает дублирования с помощью побитовых манипуляций.

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

Я обошел стороной обработку битов и просто сравнил значения индексов. Это меньше, чем значение итерации цикла (в данном случае i). Это также не будет печатать повторяющиеся пары и повторяющиеся элементы массива.

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

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

Одно из решений может быть таким, но не оптимальным (сложность этого кода - 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;
   }
}

Простая версия кода для Python, которая находит нулевую парную сумму и может быть изменена для нахождения 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

Сложность выполнения функции равна O (n) и Space: 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;
}

меньше чем o (n) решение будет =>

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

Решение на Python с использованием понимания списков

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

О (N ² )

также дает две упорядоченные пары - (a, b) и (b, a), а также

Я могу сделать это за O (n). Дай мне знать, когда захочешь получить ответ. Обратите внимание, что он включает в себя простой однократный обход массива без сортировки и т. Д. Я также должен упомянуть, что он использует коммутативность сложения и не использует хеши, но тратит впустую память.

используя Систему; using System.Collections.Generic;

/ * Существует подход O (n) с использованием таблицы поиска. Подход состоит в том, чтобы сохранить значение в «бункере», который можно легко найти (например, O (1)), если оно является кандидатом на соответствующую сумму.

например,

для каждого a [k] в массиве мы просто помещаем его в другой массив в позицию x - a [k].

Предположим, что у нас есть [0, 1, 5, 3, 6, 9, 8, 7] и x = 9

Создаем новый массив,

значение индексов

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

ТОГДА важны только те значения, которые имеют индекс в новой таблице.

Итак, скажем, когда мы достигаем 9 или равного числа, мы видим, имеет ли наш новый массив индекс 9-9 = 0. Поскольку он знает, что все содержащиеся в нем значения прибавятся к 9. (обратите внимание, что в этом случае очевидно, что есть только 1 возможный, но в нем может быть несколько значений индекса, которые нам нужно сохранить).

Таким образом, фактически нам нужно всего лишь один раз пройти через массив. Поскольку сложение коммутативно, мы получим все возможные результаты.

Например, когда мы дойдем до 6, мы получим индекс в нашей новой таблице как 9 - 6 = 3. Поскольку таблица содержит это значение индекса, мы знаем значения.

По сути, это обмен скорости на память. * /

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

Решение 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

Я сделал это при стоимости сложности O (m + n) как для времени, так и для объема памяти. Я подозреваю, что это лучший алгоритм на данный момент.

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

var z = (из a в arr из b в arr, где 10 - a == b выберите новый {a, b}). ToList;