Подсчитайте пары из двух связанных списков, сумма которых равна заданному значению


Сложный уровень средний
Часто спрашивают в саман Амазонка Avalara Expedia Фанатики Google В самом деле Microsoft PayPal Тесла
хеширования Связанный список Сортировка

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

Задача «Подсчитать пары из двух связанных списков, сумма которых равна заданному значению» означает, что вам даны два связанных списка и сумма целых значений. В постановке задачи просили узнать, сколько всего пар имеет сумму, равную заданному значению.

Пример

LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9
2

Объяснение: Есть две пары, т.е. 6, 3 и 8, 1, которые суммируют значение до заданного значения 9.

 

Алгоритм подсчета пар из связанных списков, сумма которых равна заданному значению

1. Push all the integer values to the two different linked lists.
2. Declare a set.
3. Set the count to 0.
4. Iterate over the first linked list and put all the values of it into the linked list1.
5. Iterate over the second linked list
    1. Check if the set contains the difference between the value of x and a current element of linked list2.
        1. If true then increase the value of count by 1.
6. Return count.

объяснение

В качестве входных данных мы получаем целые числа. Итак, мы поместим их все в связанные списки. В C ++ мы создали извне метод реализации связанного списка для выполнения этого решения. Но в java у нас есть встроенный класс связанного списка, с помощью которого мы можем легко вставить все значения целых чисел в связанный список. Теперь мы попросили найти пару в обоих связанных списках, в которых число суммируется с заданным значением.

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

Теперь у нас есть все значения из связанного списка 1 в наборе. Теперь мы пройдем по второму связанному списку и проверим, присутствует ли в наборе разница между x и каждым значением второго списка. Если присутствует, значит, мы нашли пару на данный момент, а также увеличим значение count на 1. Это означает, что найдена 1 пара, и она считается. В конце обхода. Значение счетчика будет номером пары, сумма которой равна заданному значению.

Подсчитайте пары из двух связанных списков, сумма которых равна заданному значению

Код:

C ++ для подсчета пар из двух связанных списков, сумма которых равна заданному значению

#include<iostream>
#include<unordered_set>

using namespace std;

struct Node
{
    int data;
    struct Node* next;
};

void implementLinkedList(struct Node** headReference, int newItem)
{
    struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

    newNode->data = newItem;

    newNode->next = (*headReference);

    (*headReference) = newNode;
}
int getPairOfsum (struct Node* head1, struct Node* head2,int sum)
{
    int count = 0;

    unordered_set<int> SET;

    while (head1 != NULL)
    {
        SET.insert(head1->data);

        head1 = head1->next;
    }

    while (head2 != NULL)
    {
        if (SET.find(sum - head2->data) != SET.end())
            count++;

        head2 = head2->next;
    }
    return count;
}
int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    implementLinkedList (&head1,11);
    implementLinkedList (&head1, 6);
    implementLinkedList (&head1, 1);
    implementLinkedList (&head1, 8);

    implementLinkedList (&head2, 5);
    implementLinkedList (&head2, 3);
    implementLinkedList (&head2, 1);
    implementLinkedList (&head2, 9);

    int sum = 9;

    cout << "Count = "<< getPairOfsum (head1, head2, sum);
    return 0;
}
Count = 2

Код Java для подсчета пар из двух связанных списков, сумма которых равна заданному значению

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

class PairOfSumInLinkedList1
{
    public static int getPairOfsum(LinkedList<Integer> head1, LinkedList<Integer> head2, int sum)
    {
        int count = 0;

        HashSet<Integer> SET = new HashSet<Integer>();

        Iterator<Integer> itr1 = head1.iterator();
        while (itr1.hasNext())
        {
            SET.add(itr1.next());

        }

        Iterator<Integer> itr2 = head2.iterator();
        while (itr2.hasNext())
        {
            if (!(SET.add(sum - itr2.next())))
                count++;

        }
        return count;
    }
    public static void main(String[] args)
    {
        Integer arr1[] = {11, 6, 1, 8};
        Integer arr2[] = {5, 3, 1, 9};

        LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));

        LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));

        int x = 9;

        System.out.println("Count = " + getPairOfsum(head1, head2, x));
    }
}
Count = 2

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

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

О (п1 + п2) в котором «N1» и «N2» - это количество элементов в связанном списке. Мы можем достичь линейной временной сложности. Потому что мы прошли по обоим связанным спискам и использовали HashSet.

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

Поскольку мы сохранили ввод в двух связанных списках и использовали HashSet. У нас есть решение с линейной пространственной сложностью.