計算來自兩個鍊錶的對,它們的和等於給定值


難度級別
經常問 土磚 亞馬遜 Avalara Expedia的 狂徒 谷歌 確實 Microsoft微軟 貝寶 特斯拉
哈希 鍊錶 排序

問題陳述

問題“從兩個等於和等於給定值的鍊錶中對數計數”狀態是給您兩個鍊錶和一個整數值之和。 問題陳述要求找出總數為給定值的總數對。

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對,並對其進行了計數。 在遍歷結束時。 count的值將是總和等於給定值的對的數量。

計算來自兩個鍊錶的對,它們的和等於給定值

推薦碼

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

複雜度分析

時間複雜度

O(n1 + n2) 哪裡 “ n1” 或 “ n2” 是鍊錶中元素的數量。 我們能夠實現線性時間複雜度。 因為我們遍歷了兩個鍊錶並使用了HashSet。

空間複雜度

由於我們將輸入存儲在兩個鏈接列表中並使用了HashSet。 我們有一個線性的空間複雜度解決方案。