Бройте двойки от два сортирани масива, чиято сума е равна на дадена стойност x  


Ниво на трудност Лесно
Често задавани в BankBazaar Cisco Цитадела Honeywell PayU Roblox Такси4 Разбира се Yandex
Array Хашиш сортиране STL

Декларация за проблема  

„Пребройте двойки от две сортирано масиви, чиято сума е равна на дадена стойност x ”, проблемът гласи, че са ви дадени два сортирани масива от цели числа и цяла стойност, наречена сума. Посочването на проблема изисква да се открие общият брой двойки, който сумира до дадена стойност.

Пример  

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 Solution

Ще зададем стойността на броя до 0. Защото ще увеличим стойността на броя с 1, ако намерим необходимата двойка. Една двойка ще се състои от две стойности. Разбира се, ще проверим дали добавянето на тази стойност в двойка е равно на дадената стойност. Ако е вярно, ще увеличим стойността на броя с 1. Ще пуснем a докато цикъл по този начин. След това ще продължи, докато стойностите на m (m е дължината на един от масива) и r (където r е едно по-малко от дължината на масив) е по-голямо от равно на 0.

В цикъл ще проверим дали стойността на двойката се добавя към дадената стойност. След това намерихме една двойка, когато това условие стане вярно. Ще продължим цикъла, ако сумата е по-малка от дадената стойност. Тогава ще увеличим стойността на l с 1 друго просто намаляваме стойността на r с 1. В крайна сметка ще върнем стойността на count.

Бройте двойки от два сортирани масива, чиято сума е равна на дадена стойност xщифт

код  

C ++ код за преброяване на двойки, чиято сума е x от два сортирани масива

#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

 

Вижте също
Заявки за обхват на обхвата без актуализации

Java код за преброяване на двойки, чиято сума е x от два сортирани масива

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) тъй като не се изисква допълнително пространство. По този начин се постига постоянна сложност в пространството.