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

난이도 쉽게
자주 묻는 질문 은행 바자 시스코 하니웰 알레그로 Roblox 택시4슈어 Yandex 주차
배열 해시 정렬 STL조회수 39

문제 정책

“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와 같은 두 개의 정렬 된 배열에서 쌍을 계산합니다.

암호

두 개의 정렬 된 배열에서 합계가 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) 추가 공간이 필요하지 않습니다. 따라서 일정한 공간 복잡성이 달성됩니다.

Translate »