ນັບຄູ່ຈາກສອງລາຍການທີ່ເຊື່ອມໂຍງເຊິ່ງຜົນລວມຂອງມັນເທົ່າກັບມູນຄ່າທີ່ໃຫ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ອາວາລາ Expedia ສະ ເໜ່ ກູໂກ ແທ້ຈິງແລ້ວ Microsoft PayPal Tesla
ແຮກ ບັນຊີທີ່ເຊື່ອມໂຍງ ຮຽງລໍາດັບ

ຖະແຫຼງການບັນຫາ

ປັນຫາ“ ນັບຄູ່ຈາກສອງລາຍການທີ່ເຊື່ອມໂຍງເຊິ່ງລວມມູນຄ່າເທົ່າກັບມູນຄ່າທີ່ລະບຸໄວ້” ສະຖານະທີ່ທ່ານໄດ້ຖືກມອບໃຫ້ສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະມີມູນຄ່າລວມ. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາໄດ້ຖາມເພື່ອຊອກຫາວ່າ ຈຳ ນວນຄູ່ທັງ ໝົດ ມີ ຈຳ ນວນເທົ່າກັບມູນຄ່າທີ່ໄດ້ມອບໃຫ້.

ຍົກຕົວຢ່າງ

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 ++, ພວກເຮົາໄດ້ສ້າງວິທີການພາຍນອກເພື່ອປະຕິບັດລາຍຊື່ທີ່ເຊື່ອມໂຍງເພື່ອ ດຳ ເນີນການແກ້ໄຂບັນຫານີ້. ແຕ່ໃນພາສາຈາວາ, ພວກເຮົາມີຊັ້ນຮຽນທີ່ຖືກສ້າງຂື້ນມາຈາກບັນຊີການເຊື່ອມໂຍງໂດຍການຊ່ວຍເຫຼືອຂອງພວກເຮົາສາມາດຍູ້ມູນຄ່າເຊື່ອມໂຍງເຂົ້າໃນບັນຊີທີ່ເຊື່ອມໂຍງເຂົ້າກັນໄດ້ຢ່າງງ່າຍດາຍ. ຕອນນີ້ພວກເຮົາໄດ້ຂໍໃຫ້ຊອກຫາຄູ່ໃນທັງສອງລາຍການທີ່ເຊື່ອມໂຍງເຊິ່ງ ຈຳ ນວນດັ່ງກ່າວຈະສະຫຼຸບໃສ່ມູນຄ່າທີ່ໄດ້ກ່າວໄວ້.

ພວກເຮົາ ກຳ ລັງຈະສົ່ງມູນຄ່າເຊື່ອມໂຍງທັງ ໝົດ ເຂົ້າໃນບັນຊີທີ່ເຊື່ອມໂຍງ. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ ທີ່ກໍານົດໄວ້ ໂຄງສ້າງຂໍ້ມູນແລະຈະ ກຳ ລັງຜ່ານທຸກຄ່າຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ 1 ແລະເກັບຄ່າທັງ ໝົດ ຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງເຂົ້າ ທຳ ອິດເພື່ອ ກຳ ນົດ. ຊຸດຍັງໃຫ້ຄຸນລັກສະນະທີ່ອົງປະກອບທົ່ວໄປຖືກຍ້າຍອອກໂດຍອັດຕະໂນມັດຈາກຊຸດ. ສະນັ້ນຖ້າພວກເຮົາໃນຄັ້ງຕໍ່ໄປພວກເຮົາຈະໃຊ້ຊຸດທີ່ບໍ່ມີບັນຫາ ສຳ ລັບອົງປະກອບ ທຳ ມະດາ, ແລະມັນກໍ່ຈະບໍ່ມີສ່ວນປະກອບ ທຳ ມະດາໃດ ໜຶ່ງ ຢູ່ໃນນັ້ນຢູ່ໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງ.

ຕອນນີ້ພວກເຮົາມີຄຸນຄ່າທັງ ໝົດ ໃນລາຍຊື່ທີ່ເຊື່ອມໂຍງ 1 ເຂົ້າໃນຊຸດ. ຕອນນີ້ພວກເຮົາຈະລວບລວມບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງຄັ້ງທີສອງແລະກວດເບິ່ງວ່າຄວາມແຕກຕ່າງລະຫວ່າງ x ແລະແຕ່ລະຄ່າຂອງບັນຊີລາຍຊື່ທີສອງມີຢູ່ໃນຊຸດຫລືບໍ່. ຖ້າປະຈຸບັນພວກເຮົາໄດ້ພົບຄູ່ແລ້ວ ສຳ ລັບດຽວນີ້ແລະພວກເຮົາກໍ່ຈະເພີ່ມມູນຄ່າການນັບໂດຍ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n1 + n2) ບ່ອນທີ່ "n1" ແລະ "n2" ແມ່ນຕົວເລກຂອງສ່ວນປະກອບໃນບັນຊີທີ່ເຊື່ອມໂຍງ. ພວກເຮົາສາມາດບັນລຸຄວາມສັບສົນທີ່ໃຊ້ເວລາເປັນເສັ້ນ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ຜ່ານທັງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະໃຊ້ HashSet.

ຄວາມສັບສົນໃນອະວະກາດ

ນັບຕັ້ງແຕ່ພວກເຮົາເກັບຮັກສາວັດສະດຸປ້ອນເຂົ້າໃນສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະໃຊ້ HashSet. ພວກເຮົາມີວິທີແກ້ໄຂບັນຫາຄວາມສັບສົນໃນເສັ້ນຊື່.