합이 C++에서 주어진 값 x와 같은 두 개의 정렬된 배열에서 쌍을 셉니다.

<시간/>

양수와 값 x를 포함하는 두 개의 배열이 제공됩니다. 목표는 (A, B) 유형의 쌍이 A+B=x이고 A가 첫 번째 배열에 속하고 B가 두 번째 배열에 속하도록 배열 요소 쌍을 찾는 것입니다.

예를 들어 이해하자

입력 - arr_1[] ={1,2,5,3,4}; arr_2[] ={7,0,1,3}; x=6

출력 −합이 주어진 값 x와 같은 두 개의 정렬된 배열에서 쌍의 개수는 − 2

설명 − 쌍은 (5,1) - (arr_1[2],arr_2[2]) 및 (3,3) - (arr_1[3],arr_2[3])

입력 - arr_1[] ={1,1,1}; arr_2[] ={2,2}; x=6

출력 - 합이 주어진 값 x와 같은 두 개의 정렬된 배열에서 쌍의 개수는 - 2

설명 − 쌍은 (1,2) - (arr_1[0],arr_2[0]) 및 (1,2) - (arr_1[1],arr_2[1])

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

우리는 두 가지 접근 방식을 사용할 것입니다. for 루프를 사용하는 최초의 순진한 접근 방식. 인덱스 i가 arr_1[]용이고 인덱스 j가 arr_2[]용이 되도록 for 루프를 사용하여 둘 다 탐색을 시작합니다. 쌍(arr_1[i]+arr_2[j]==x)의 경우 카운트를 증가시킵니다. 결과로 카운트를 반환합니다.

양수 요소와 길이를 size_arr_1 및 size_arr_2로 포함하는 정수 배열 arr_1[] 및 arr_2[]를 사용합니다.
함수 Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x)는 배열과 배열의 길이를 모두 취하고 요소의 합이 x가 되도록 쌍을 반환합니다.
count의 초기값을 0으로 합니다.
i=0에서 i로 arr_1[] 순회 시작
각 쌍에 대해 arr_1[i], arr_2[j] 합계가 x인지 확인합니다. true이면 카운트를 증가시킵니다.
결과로 카운트를 반환합니다.

효율적인 접근

이 접근 방식에서 우리는 rr_1 요소의 unordered_set을 생성할 것입니다. 이제 for 루프를 사용하여 arr_2를 순회하고 각 값 arr_2[i]에 대해 x-arr_2[i]가 세트에서 발견되면 카운트를 증가시킵니다. 마지막에 카운트를 반환합니다.

동일한 배열과 크기를 사용합니다.
함수 Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x)는 배열과 배열의 길이를 모두 취하고 요소의 합이 x가 되도록 쌍을 반환합니다.
초기 카운트를 0으로 합니다.
arr_1의 고유한 요소를 저장하기 위해 unordered_set hash_map을 만듭니다.
for 루프를 사용하여 arr_1의 요소로 hash_map을 채웁니다.
이제 for 루프를 사용하여 arr_2[]를 탐색합니다.
각 arr-2[j]에 대해 x-arr_2[j]가 (hash_map.find(x - arr_2[j]) !=hash_map.end())를 사용하여 hash_map에서 발견되면 카운트를 증가시킵니다.
마지막에 합계가 x인 쌍으로 계산합니다.
결과로 카운트를 반환합니다.

예(순진한 접근 방식)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   for (int i = 0; i < size_arr_1; i++){
      for (int j = 0; j < size_arr_2; j++){
         if ((arr_1[i] + arr_2[j]) == x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<<
Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4

예시(효율적인 접근)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   unordered_set<int> hash_map;
   for (int i = 0; i < size_arr_1; i++){
      hash_map.insert(arr_1[i]);
   }
   for (int j = 0; j < size_arr_2; j++){
      if (hash_map.find(x - arr_2[j]) != hash_map.end()){
         count++;
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4