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

## 例

```LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9```
`2`

## 從鍊錶中對數等於和等於給定值的對進行計數的算法

```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 ++從兩個鍊錶中對對進行計數，兩個鍊錶的和等於給定值

```#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。