Հաշվեք զույգերը երկու տեսակավորված զանգվածներից, որոնց գումարը հավասար է տրված x արժեքին  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են BankBazaar Cisco Միջնաբերդ HONEYWELL PayU Roblox Taxi4Sure- ը Yandex
Դասավորություն Խանգարել դասավորում 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 լուծում

Մենք պատրաստվում ենք սահմանել հաշվել մինչեւ 0. Քանի որ հաշվարկի այդ արժեքը 1-ով կավելացնենք, եթե գտնենք պահանջվող զույգը: Aույգը բաղկացած կլինի երկու արժեքից: Իհարկե, մենք պատրաստվում ենք ստուգել, ​​արդյոք այդ արժեքի ավելացումը զույգում հավասար է տրված արժեքի գումարին: Եթե ​​դա ճիշտ է, մենք կավելացնենք հաշվարկի արժեքը 1.-ով: Մենք գործարկելու ենք a իսկ հանգույց այս ոճով. Այնուհետև այն կգնա այնքան ժամանակ, քանի դեռ m- ի (m- ն զանգվածի մեկի երկարությունն է) և r- ի (որտեղ r- ը զանգվածի երկարությունից մեկով պակաս) արժեքներն ավելի մեծ են, քան հավասար են 0-ի:

Օղակում մենք ստուգելու ենք, թե արդյոք զույգի արժեքը գումարվում է տրված արժեքին: Հետո, մենք գտնում ենք մեկ զույգ, երբ այս պայմանն իրականանա: Մենք կշարունակենք օղակը, եթե գումարը պակաս լինի տրված արժեքից: Այդ ժամանակ մենք կբարձրացնենք արժեքը l ևս 1-ով մենք պարզապես իջեցնում ենք արժեքը r վերջ 1. մենք վերջում կվերադարձնենք հաշվարկի արժեքը:

Հաշվեք զույգերը երկու տեսակավորված զանգվածներից, որոնց գումարը հավասար է տրված x արժեքինPin

Կոդ  

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

 

Բարդության վերլուծություն  

Timeամանակի բարդություն

Ո (մ + ն) որտեղ «Մ» և «Ն» arr1- ում և arr- ում տարրերի քանակն է: Քանի որ առավելագույնը, որով կարող ենք ճանապարհորդել, m + n է:

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: Այսպիսով, տարածության անընդհատ բարդությունը ձեռք է բերվում: