Суммасы берилген хге барабар болгон эки иреттелген массивден жуптарды эсептеңиз  


Кыйынчылык деңгээли жеңил
Көп суралган BankBazaar Cisco Citadel ЭлЭлПи PayU Roblox Taxi4Sure Яндекс
согуштук тизме таштанды сорттоо ЛИС

Маселени билдирүү  

«Эки жуптан сана сорттолгон суммасы берилген мааниге барабар болгон массивдер 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 жуп бар.

Суммасы берилген хге барабар болгон эки иреттелген массивден жуптарды саноонун алгоритми  

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.

түшүндүрүү

Сизге эки иреттелген бүтүн сан берилет Arrays жана сумма деп аталган бүтүн сан. Жана берилген мааниге чейин канча мүмкүн болгон түгөйлөрдү түзсө болоорун сурадык. Ошентип, экилик издөө ыкмасы катары ушул сыяктуу техниканы колдонобуз. Киргизилген баалуулуктарды жогорулаган тартипте алып жаткандыгыбыздын себеби да ушул. Ошентип, биз ушул суроону чечүүдө ошол ыкманы колдоно алабыз. Башка учурда биз массивди иреттеп алмакпыз.

ошондой эле
Дизайн парк тутумунун чечими

Биз анын маанисин коёбуз эсептөө 0го чейин. Себеби, эгер керектүү түгөйдү тапсак, эсептөөнүн маанисин 1ге көбөйтөбүз. Жуп эки мааниден турат. Албетте, ошол маанинин жупка кошулушу берилген маани суммасына барабар экендигин текшеребиз. Эгер чын болсо, биз эсептөөнүн маанисин 1ге көтөрөбүз while цикл ушул тартипте. Андан кийин m (m - массивдин биринин узундугу) жана r (бул жерде массивдин узундугунан бир аз) мааниси 0гө барабар болгонго чейин барат.

Циклда, жуптун мааниси берилген мааниге чейин кошулгандыгын текшеребиз. Андан кийин, ушул шарт орундалган сайын бир жуп таптык. Эгерде сумма берилген мааниден аз болсо, биз циклин улантабыз. Ошондо биз анын маанисин көтөрөбүз l дагы 1ге биз жөн эле маанисин төмөндөтөбүз r 1. Акыр-аягы, биз эсептөөнүн маанисин кайтарып беребиз.

Суммасы берилген хге барабар болгон эки иреттелген массивден жуптарды эсептеңизтөөнөч

коду  

С ++ коду, эки сорттолгон массивдин суммасы х болгон жуптарды эсептөө

#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 коду

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) кайда "М" жана "N" arr1 жана arr2 элементтеринин саны. Себеби биз бара турган максимум m + n.

Космостун татаалдыгы

O (1) ашыкча орун талап кылынбагандыктан. Ошентип туруктуу космостук татаалдыкка жетишилет.