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

Ответ 1

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

Ответ 2

Существует 3 подхода к этому решению:

Пусть сумма равна T и n - размер массива

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


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


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

Вы можете указать здесь здесь. Спасибо.

Ответ 3

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

}
}

Для ввода = {2,45,7,3,5,1,8,9} и если Sum 10

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

3,7 
8,2
9,1

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

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

Ответ 4

Решение в 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);
    }
}

Ответ 5

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

Ответ 6

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

Ответ 7

Вот решение, которое учитывает дубликаты записей. Он написан в 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

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

Ответ 8

О (п)

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

Ответ 9

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

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

Ответ 10

Реализация в 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) map.get(k-a [i])!= I из условия if, и вам хорошо идти.

Ответ 11

это реализация 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;
}

Ответ 12

В 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

Ответ 13

Хорошее решение от 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]

Ответ 14

Вот код 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 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]+")");
        }
    }
}

}

Ответ 15

Простая программа в 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]);
       }
    }
}

Ответ 16

Простой фрагмент кода 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);
        }
    }
    }

Ответ 17

Другое решение в 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)

Ответ 18

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

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

Ответ 19

Я обошел бит-мануляцию и просто сравнил значения индекса. Это меньше, чем значение итерации цикла (в этом случае - 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);
            }
        }
    }
}

Ответ 20

в С#:

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

Ответ 21

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

Ответ 22

Простая версия кода на основе 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).

Ответ 23

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

Ответ 24

https://github.com/clockzhong/findSumPairNumber

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

Ответ 25

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

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

Ответ 26

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

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

O (N ²)

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

Ответ 27

Мое решение - 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("------------------------------");
}

Ответ 28

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

используя Систему; использование 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();
        }
    }
}

Ответ 29

Решение для 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);
}

Ответ 30

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

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