차례
문제 정책
“XNUMX 개에서 쌍을 센다 분류 합이 주어진 값 x와 같은 배열”문제는 두 개의 정렬 된 정수 배열과 sum이라는 정수 값이 주어 졌다는 것을 나타냅니다. 문제 설명은 주어진 값을 합산하는 총 쌍 수를 알아 내도록 요청합니다.
예
arr1[] = {1, 6, 8, 11}
arr2[] = {1, 3, 5, 9}
sum = 9
2
설명 : 주어진 배열에는 (2, 6) 및 (3, 8)의 총 1 개의 쌍이 있기 때문입니다. 다른 쌍의 합계가 필요한 합계보다 크거나 작기 때문입니다.
arr1[] = {3, 5, 11, 14};
arr2[] = {2, 4, 5, 11}
sum = 16
3
설명 : 주어진 배열에 (3, 5), (11, 11) 및 (5, 14)의 총 2 개의 쌍이 있기 때문입니다.
합이 주어진 값 x와 같은 두 개의 정렬 된 배열에서 쌍을 계산하는 알고리즘
1. Set count and left to 0, and right to n-1 where n is the length of the array.
2. While left is less than m and right is greater than equal to 0, repeat the following the steps-
1. If the sum of arr[left] and arr[right] is equal to the given value, then increase the value of count and left by 1 and decrease the value of right by 1.
2. Else check if the addition of arr[left] and arr[right] is less than the given value sum, then increase the value of left by 1.
3. Decrease the value of right by 1 if the addition is greater than the sum.
3. Return the count value after traversing the arrays.
설명
두 개의 정렬 된 정수가 제공됩니다. 배열 합계라는 정수 값이 있습니다. 그리고 주어진 값을 합산 할 수있는 가능한 쌍이 몇 개나 형성 될 수 있는지 알아 내야합니다. 그래서 우리는 이진 검색 방법과 유사한 기술을 사용할 것입니다. 이것이 입력 값을 오름차순으로 취하는 이유이기도합니다. 이런 식으로 우리는이 문제를 해결하는 데 그 기술을 적용 할 수 있습니다. 그렇지 않으면 배열을 정렬했을 것입니다.
우리는 값을 설정할 것입니다 계산 왜냐하면 필요한 쌍을 찾으면 카운트 값을 0만큼 증가시킬 것이기 때문입니다. 쌍은 두 개의 값으로 구성됩니다. 물론, 우리는 한 쌍에 그 값을 더한 것이 주어진 값의 합과 같은지 확인할 것입니다. 사실이면 count 값을 1 씩 늘릴 것입니다. while 루프 이런 방법으로. 그런 다음 m 값 (m은 배열 중 하나의 길이)과 r (여기서 r은 배열 길이보다 작음) 값이 0보다 클 때까지 이동합니다.
루프에서 쌍의 값이 주어진 값에 더해지는 지 확인합니다. 그런 다음이 조건이 참이 될 때마다 한 쌍을 찾았습니다. 합계가 주어진 값보다 작 으면 루프를 계속합니다. 그런 다음 우리는 l 그렇지 않으면 우리는 단지 r 마지막으로 count 값을 반환합니다.
암호
두 개의 정렬 된 배열에서 합계가 x 인 쌍을 계산하는 C ++ 코드
#include<iostream>
using namespace std;
int getPairofsum(int arr1[], int arr2[], int m, int n, int sum)
{
int count = 0;
int left = 0, right = n - 1;
while (left < m && right >= 0)
{
if ((arr1[left] + arr2[right]) == sum)
{
left++;
right--;
count++;
}
else if ((arr1[left] + arr2[right]) < sum)
left++;
else
right--;
}
return count;
}
int main()
{
int arr1[] = {1, 6, 8, 11};
int arr2[] = {1, 3, 5, 9};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int sum = 9;
cout << "Count = "<< getPairofsum(arr1, arr2, m, n, sum);
return 0;
}
Count = 2
두 개의 정렬 된 배열에서 합계가 x 인 쌍을 계산하는 Java 코드
class PairofSum
{
public static int getPairofsum(int arr1[],int arr2[], int m, int n, int sum)
{
int count = 0;
int left = 0, right = n - 1;
while (left < m && right >= 0)
{
if ((arr1[left] + arr2[right]) == sum)
{
left++;
right--;
count++;
}
else if ((arr1[left] + arr2[right]) < sum)
left++;
else
right--;
}
return count;
}
public static void main (String[] args)
{
int arr1[] = {1, 6, 8, 11};
int arr2[] = {1, 3, 5, 9};
int m = arr1.length;
int n = arr2.length;
int sum = 9;
System.out.println( "Count = "+ getPairofsum(arr1, arr2, m, n, sum));
}
}
Count = 2
복잡성 분석
시간 복잡성
O (m + n) 어디에 "엠" 및 "엔" arr1 및 arr2의 요소 수입니다. 우리가 이동할 수있는 최대 값은 m + n이기 때문입니다.
공간 복잡성
O (1) 추가 공간이 필요하지 않습니다. 따라서 일정한 공간 복잡성이 달성됩니다.
