Падлічыце пары з двух адсартаваных масіваў, сума якіх роўная зададзенаму значэнню х


Узровень складанасці Лёгка
Часта пытаюцца ў БанкБазар Cisco Citadel Honeywell PayU Roblox Таксі4Упэўнена Яндэкс
масіў гашыш сартаванне СТЛ

Пастаноўка праблемы

«Палічыце пары з двух адсартаваныя масівы, сума якіх роўная дадзенаму значэнню х », праблема сцвярджае, што вам даюцца два адсартаваныя масівы цэлых лікаў і цэлае значэнне, якое называецца сума. Пастаноўка задачы патрабуе высветліць агульную колькасць пары, якое складае да зададзенага значэння.

Прыклад

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

Алгарытм падліку пар з двух адсартаваных масіваў, сума якіх роўная зададзенаму значэнню х

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.

Тлумачэнне

Вам дадзена два адсартаваныя цэлыя лікі масівы і цэлае значэнне, якое называецца sum. І нас просяць даведацца, колькі магчымых пар можа скласціся, што складае да зададзенага значэння. Такім чынам, мы збіраемся выкарыстаць падобны прыём як бінарны метад пошуку. Гэта таксама прычына, па якой мы прымаем значэнні ўводу ў парадку павелічэння. Такім чынам, мы зможам прымяніць гэтую тэхніку пры вырашэнні гэтага пытання. Інакш мы б адсартавалі масіў.

Мы збіраемся ўсталяваць значэнне лічыць да 0. Паколькі мы павялічым гэтае значэнне ліку на 1, калі знойдзем патрэбную пару. Пара будзе складацца з двух значэнняў. Зразумела, мы будзем правяраць, ці складанне гэтага значэння ў пары роўна зададзенай суме значэння. Калі гэта праўда, мы павялічым значэнне count на 1. Мы запусцім a у той час як цыкл такім чынам. Тады ён будзе ісці, пакуль значэнні m (m - даўжыня аднаго з масіва) і r (дзе r на адзін менш, чым даўжыня масіва) не будуць большыя за роўныя 0.

У цыкле мы праверым, ці павялічваецца значэнне пары да зададзенага значэння. Затым мы знаходзім адну пару, калі гэты стан становіцца сапраўдным. Мы будзем працягваць цыкл, калі сума будзе меншай за зададзенае значэнне. Тады мы павялічым значэнне l на 1 яшчэ мы проста памяншаем значэнне r па 1. У рэшце рэшт мы вернем значэнне count.

Падлічыце пары з двух адсартаваных масіваў, сума якіх роўная зададзенаму значэнню х

код

Код 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) бо дадатковае месца не патрабуецца. Такім чынам дасягаецца пастаянная складанасць прасторы.