ນັບຄູ່ຈາກສອງຂບວນທີ່ຈັດລຽງ ລຳ ດັບເຊິ່ງລວມເທົ່າກັບມູນຄ່າທີ່ໃຫ້ x


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ທະນາຄານ BankBazaar Cisco Citadel Honeywell PayU ຟລີໂຄ້ດ Taxi4Sure Yandex
Array Hash ຮຽງລໍາດັບ ຕ. ລ

ຖະແຫຼງການບັນຫາ

“ ນັບຄູ່ຈາກສອງ ຈັດຮຽງ arrays ຊຶ່ງລວມຂອງມັນເທົ່າກັບຄ່າທີ່ໃຫ້ 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.

ຄໍາອະທິບາຍ

ທ່ານໄດ້ຖືກມອບໃຫ້ສອງຕົວເລກເຕັມ ອາຄານ ແລະມູນຄ່າເລກເຕັມເອີ້ນວ່າຜົນລວມ. ແລະພວກເຮົາຖືກຂໍໃຫ້ຄົ້ນຫາຄູ່ຄູ່ທີ່ເປັນໄປໄດ້ທີ່ສາມາດສ້າງຕັ້ງຂຶ້ນເຊິ່ງສະຫຼຸບເຖິງມູນຄ່າທີ່ໄດ້ຮັບ. ສະນັ້ນ, ພວກເຮົາຈະໃຊ້ເຕັກນິກທີ່ຄ້າຍຄືກັນນີ້ເປັນວິທີການຄົ້ນຫາຖານສອງ. ນີ້ກໍ່ແມ່ນເຫດຜົນທີ່ພວກເຮົາປະຕິບັດຄຸນຄ່າການປ້ອນຂໍ້ມູນເຂົ້າໃນລະບຽບທີ່ເພີ່ມຂື້ນ. ດ້ວຍວິທີນີ້, ພວກເຮົາຈະສາມາດ ນຳ ໃຊ້ເຕັກນິກດັ່ງກ່າວໃນການແກ້ໄຂ ຄຳ ຖາມນີ້. ອື່ນພວກເຮົາຈະໄດ້ຈັດຮຽງແຖວ.

ພວກເຮົາ ກຳ ນົດຄ່າຂອງ ນັບ ເຖິງ 0. ເພາະວ່າພວກເຮົາຈະເພີ່ມມູນຄ່ານັ້ນນັບ 1 ໂດຍຖ້າພວກເຮົາພົບຄູ່ທີ່ຕ້ອງການ. ຄູ່ຈະປະກອບດ້ວຍສອງຄ່າ. ແນ່ນອນ, ພວກເຮົາຈະກວດສອບວ່າການເພີ່ມມູນຄ່ານັ້ນໃນຄູ່ແມ່ນເທົ່າກັບຍອດລວມມູນຄ່າທີ່ໄດ້ມອບໃຫ້. ຖ້າວ່າມັນແມ່ນຄວາມຈິງພວກເຮົາຈະເພີ່ມມູນຄ່າການນັບໂດຍ 1. ພວກເຮົາຈະແລ່ນ a ໃນຂະນະທີ່ loop ໃນລັກສະນະນີ້. ຫຼັງຈາກນັ້ນມັນຈະໄປຈົນກ່ວາຄ່າຂອງ m (m ແມ່ນຄວາມຍາວຂອງ ໜຶ່ງ ຂອງຂບວນ) ແລະ r (ບ່ອນທີ່ r ແມ່ນ ໜຶ່ງ ກ່ວາຄວາມຍາວຂອງຂບວນ) ແມ່ນໃຫຍ່ກວ່າ 0 ເທົ່າກັບ XNUMX.

ໃນວົງຈອນ, ພວກເຮົາຈະກວດເບິ່ງວ່າມູນຄ່າຂອງຄູ່ເພີ່ມຂຶ້ນກັບມູນຄ່າທີ່ໄດ້ມອບໃຫ້. ຈາກນັ້ນ, ພວກເຮົາໄດ້ພົບຄູ່ ໜຶ່ງ ທຸກຄັ້ງທີ່ສະພາບການນີ້ກາຍເປັນຄວາມຈິງ. ພວກເຮົາຈະສືບຕໍ່ໃນວົງຈອນຖ້າຜົນລວມ ໜ້ອຍ ກວ່າມູນຄ່າທີ່ໃຫ້ໄວ້. ຫຼັງຈາກນັ້ນພວກເຮົາຈະເພີ່ມມູນຄ່າຂອງ l ໂດຍ 1 ອີກພວກເຮົາພຽງແຕ່ຫລຸດຄຸນຄ່າຂອງ r ໂດຍ 1. ໃນທີ່ສຸດ, ພວກເຮົາຈະສົ່ງຄືນຄ່າຂອງການນັບ.

ນັບຄູ່ຈາກສອງຂບວນທີ່ຈັດລຽງ ລຳ ດັບເຊິ່ງລວມເທົ່າກັບມູນຄ່າທີ່ໃຫ້ 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) ບ່ອນທີ່ "m" ແລະ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນ arr1 ແລະ arr2. ເພາະວ່າສູງສຸດທີ່ພວກເຮົາສາມາດເດີນທາງແມ່ນ m + n.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ຍ້ອນວ່າບໍ່ ຈຳ ເປັນຕ້ອງມີພື້ນທີ່ພິເສດ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຄົງທີ່ຈຶ່ງບັນລຸໄດ້.