นับคู่จากสองอาเรย์ที่เรียงแล้ว ที่ผลรวมเท่ากับค่า x ใน C++

เราได้รับสองอาเรย์ที่มีจำนวนบวกและค่า x เป้าหมายคือหาคู่ของสมาชิกอาเรย์ที่คู่แบบ (A, B) มี A+B=x และ A 属于อาเรย์แรก และ B 属于อาเรย์ที่สอง

มาดูตัวอย่าง

อินพุต − arr_1[] = {1,2,5,3,4}; arr_2[] = {7,0,1,3}; x=6

เอาต์พุต − จำนวนคู่จากสองอาเรย์ที่เรียงแล้วที่ผลรวมเท่ากับค่า x คือ 2

คำอธิบาย − คู่คือ (5,1) - (arr_1[2],arr_2[2]) และ (3,3) - (arr_1[3],arr_2[3])

อินพุต − arr_1[] = {1,1,1}; arr_2[] = {2,2}; x=6

เอาต์พุต − จำนวนคู่จากสองอาเรย์ที่เรียงแล้วที่ผลรวมเท่ากับค่า x คือ 2

คำอธิบาย − คู่คือ (1,2) - (arr_1[0],arr_2[0]) และ (1,2) - (arr_1[1],arr_2[1])

แนวทางที่ใช้ในโปรแกรม

เราจะใช้สองวิธี วิธีแรกแบบง่ายด้วยลูป FOR เริ่มเดินทางทั้งสองด้วยลูป FOR ที่ดัชนี i สำหรับ arr_1[] และดัชนี j สำหรับ arr_2[] สำหรับคู่ (arr_1[i]+arr_2[j]==x) เพิ่ม count คืน count

• รับอาเรย์จำนวนเต็ม arr_1[] และ arr_2[] พร้อมความยาว size_arr_1 และ size_arr_2
• ฟังก์ชัน Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) รับทั้งสองอาเรย์และความยาว คืนคู่ที่ผลรวมสมาชิกเป็น x
• กำหนดค่าเริ่มต้นของ count เป็น 0
• เริ่มเดินทาง arr_1[] จาก i=0 ถึง i<size_arr_1 และ arr_2[] จาก j=0 ถึง j<size_arr_2
• สำหรับแต่ละคู่ arr_1[i], arr_2[j] ตรวจสอบถ้าผลรวมเป็น x ถ้าจริงเพิ่ม count
• คืน count

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้เราจะสร้าง unordered_set ของสมาชิก arr_1 ตอนนี้เดินทาง arr_2 ด้วยลูป FOR และสำหรับแต่ละค่า arr_2[i] ถ้า x-arr_2[i] พบในเซต ให้เพิ่ม count คืน count ท้ายสุด

• รับอาเรย์เดียวกันและขนาด
• ฟังก์ชัน Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x) รับทั้งสองอาเรย์และความยาว คืนคู่ที่ผลรวมสมาชิกเป็น x
• กำหนด count เริ่มต้น 0
• สร้าง unordered_set<int> hash_map สำหรับเก็บสมาชิกไม่ซ้ำของ arr_1
• เติม hash_map ด้วยสมาชิกของ arr_1 ด้วยลูป FOR
• ตอนนี้เดินทาง arr_2[] ด้วยลูป FOR
• สำหรับแต่ละ arr_2[j] ถ้า x-arr_2[j] พบใน hash_map ด้วย (hash_map.find(x - arr_2[j]) != hash_map.end()) เพิ่ม count
• ท้ายสุด count เป็นคู่ที่ผลรวมเท่ากับ x
• คืน count

ตัวอย่าง (วิธีง่าย)

#include <bits/stdc++.h>
using namespace std;

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
    int count = 0;
    for (int i = 0; i < size_arr_1; i++){
        for (int j = 0; j < size_arr_2; j++){
            if ((arr_1[i] + arr_2[j]) == x){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4

ตัวอย่าง (แนวทางมีประสิทธิภาพ)

#include <bits/stdc++.h>
using namespace std;

int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
    int count = 0;
    unordered_set<int> hash_map;
    for (int i = 0; i < size_arr_1; i++){
        hash_map.insert(arr_1[i]);
    }
    for (int j = 0; j < size_arr_2; j++){
        if (hash_map.find(x - arr_2[j]) != hash_map.end()){
            count++;
        }
    }
    return count;
}

int main(){
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4