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


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

문제 정책  

“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.

설명

두 개의 정렬 된 정수가 제공됩니다. 배열 합계라는 정수 값이 있습니다. 그리고 주어진 값을 합산 할 수있는 가능한 쌍이 몇 개나 형성 될 수 있는지 알아 내야합니다. 그래서 우리는 이진 검색 방법과 유사한 기술을 사용할 것입니다. 이것이 입력 값을 오름차순으로 취하는 이유이기도합니다. 이런 식으로 우리는이 문제를 해결하는 데 그 기술을 적용 할 수 있습니다. 그렇지 않으면 배열을 정렬했을 것입니다.

참조
주차 시스템 Leetcode 솔루션 설계

우리는 값을 설정할 것입니다 계산 왜냐하면 필요한 쌍을 찾으면 카운트 값을 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) 추가 공간이 필요하지 않습니다. 따라서 일정한 공간 복잡성이 달성됩니다.