Для двух несортированных массивов найдите все пары, сумма которых равна x


Сложный уровень Легко
Часто спрашивают в Амазонка Facebook
массив Hash хеширования

Постановка задачи

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

Пример

arr1[] = { 3,6,1,4,8,2}

arr2[] = { 2,1,5,7,2,4}

sum = 9
(8, 1), (4, 5) (2, 7)

Объяснение: У всех трех пар есть число, сумма которого равна заданному значению 9.

arr1[] = { 2,5,1,7,9}

arr2[] = { 3,6,8,1,0}

sum = 7
(1, 6), (7, 0)

Объяснение: Обе пары имеют число, сумма которого равна заданному значению 7.

Алгоритм поиска всех пар, имеющих sum = x, в двух несортированных массивах

1. Declare a Set.
2. Insert all the values of array1 into the Set.
3. Traverse the array2.
4. Check if the difference of sum and each number of array2 is present in a set.
5. If present then prints the difference and the current array element.

объяснение

Для двух несортированных массивов найдите все пары, сумма которых равна x. Для этого воспользуемся набором. В комплекте также предусмотрена возможность удаления общих элементов. Что мы собираемся сделать, так это вставить в набор все значения array1. Здесь, если установлено, удаляет или не удаляет элементы. Нас это не волнует, потому что нам нужно только число, чтобы проверить, можно ли сформировать пару.

Обходя первый массив, мы будем вставлять все его значения в набор. Позже, с помощью этого набора, мы выясним, есть ли у нас какая-либо пара, которая может быть сформирована, сумма которой равна заданному значению, называемому суммой. Когда мы закончим вставку всех значений в набор, мы перейдем к массиву 2.

Начиная с первого элемента второго массива, мы будем проверять разницу между заданным значением и каждым значением второго массива при обходе. Это похоже на то, что мы можем сложить два числа, например, a + b = c, и теперь, если у нас есть только b и c, с помощью cb мы можем найти 'a'. То же самое и здесь, у нас есть результирующее значение, мы можем узнать, какое значение требуется для завершения пары. Вот почему мы ищем разницу суммы и каждого значения array2 в array1. Если мы найдем пары, просто напечатайте разницу между парой и текущим элементом массива, это будет необходимая пара.

Для двух несортированных массивов найдите все пары, сумма которых равна x

Код:

Код C ++ для поиска всех пар, имеющих sum = x, в двух несортированных массивах

#include<iostream>
#include<unordered_set>

using namespace std;

void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
{
    unordered_set<int> MAP;
    for (int i = 0; i < l1; i++)
        MAP.insert(arr1[i]);

    for (int j = 0; j < l2; j++)
        if (MAP.find(sum - arr2[j]) != MAP.end())
            cout << sum - arr2[j] << " "<< arr2[j] << endl;
}
int main()
{
    int arr1[] = { 3,6,1,4,8,2};
    int arr2[] = { 2,1,5,7,2,4};
    int sum = 9;
    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);
    getPairsofSum(arr1, arr2, l1, l2, sum);
    return 0;
}
8 1
4 5
2 7

 

Код Java для поиска всех пар, имеющих sum = x, в двух несортированных массивах

import java.util.HashMap;

class PairofSumUnsortedArray
{
    public static void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        for (int i = 0; i < l1; i++)
            MAP.put(arr1[i], 0);

        for (int j = 0; j < l2; j++)
            if (MAP.containsKey(sum - arr2[j]))
                System.out.println(sum - arr2[j] + " " + arr2[j]);
    }
    public static void main(String[] args)
    {
        int arr1[] = { 3,6,1,4,8,2};
        int arr2[] = { 2,1,5,7,2,4};
        int sum = 9;
        getPairsofSum(arr1, arr2, arr1.length, arr2.length, sum);
    }
}
8 1
4 5
2 7

 

Анализ сложности

Сложность времени

O (макс (п, м)) в котором «Н» и «М» - длина первого и второго массива.

Космическая сложность

O (макс (п, м)) в котором «Н» и «М» - длина первого и второго массива.