การหาคู่ที่มีผลรวมกำหนดในเมทริกซ์ โดยใช้ C++

ในบทความนี้ เราจะอภิปรายโปรแกรมการหาคู่ที่มีผลรวมที่กำหนดในเมทริกซ์ที่กำหนด ตัวอย่างเช่น:

Input : matrix[n][m] = {
    { 4, 6, 4, 65 },
    { 56, 1, 12, 32 },
    { 4, 5, 6, 44 },
    { 13, 9, 11, 25 } }, SUM = 20
Output : Pair exists.
คำอธิบาย : Sum = 20 เท่ากับผลรวมของตัวเลข 9 และ 11 ซึ่งมีอยู่ในเมทริกซ์

Input : matrix[n][m] = {
    { 5, 7, 3, 45 },
    { 63, 5, 3, 7 },
    { 11, 6, 9, 5 },
    { 8, 6, 14, 15 } }, SUM = 13
Output : Pair does not exist.
คำอธิบาย : ไม่มีคู่ในเมทริกซ์ที่ผลรวมเท่ากับ 13

วิธีการแก้ปัญหา

ตอนนี้เราจะอธิบายสองวิธีที่แตกต่างกันเพื่อหาคำตอบของปัญหาข้างต้น

วิธี Brute-Force

พิจารณาแต่ละคู่ในเมทริกซ์ที่กำหนดและตรวจสอบว่าผลรวมของคู่นั้นเท่ากับ SUM ที่กำหนดหรือไม่ ถ้าใช่ พิมพ์ "Pair exists" มิฉะนั้น พิมพ์ "Pair does not exist" การนำวิธีนี้มาใช้ง่ายมาก แต่จะทำให้ความซับซ้อนด้านเวลาพุ่งสูงเป็น O((N×M)²)

วิธีที่มีประสิทธิภาพ (Efficient Approach)

โปรแกรมนี้สามารถมีประสิทธิภาพได้โดยการใช้ hash เพื่อเก็บองค์ประกอบทั้งหมดของเมทริกซ์ และจากนั้นเดินทางผ่านเมทริกซ์และตรวจสอบว่าความต่างของ [ SUM และ (องค์ประกอบดัชนี) ] มีอยู่หรือไม่ ถ้าใช่ พิมพ์ "Exist" และออกจากโปรแกรม ถ้าไม่ หลังจากเดินทางผ่าน พิมพ์ "does not exist"

ตัวอย่าง

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

#define n 4
#define m 4

int main() {
    int matrix[n][m] = {
        { 5, 7, 3, 45 },
        { 63, 5, 3, 7 },
        { 11, 6, 9, 5 },
        { 8, 6, 14, 15 }
    };
    int sum = 7;
    unordered_set hash;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (hash.find(sum - matrix[i][j]) != hash.end()) {
                cout << "Pair exists." << endl;
                return 0;
            } else {
                hash.insert(matrix[i][j]);
            }
        }
    }
    cout << "Pair does not exist." << endl;
    return 0;
}

ผลลัพธ์

Pair does not exist.

คำอธิบายโค้ด

• ประกาศอาร์เรย์ 2 มิติและเก็บองค์ประกอบไว้
• เดินทางผ่านอาร์เรย์ หา if (sum - matrix[i][j]) != hash.end()
• ถ้าเงื่อนไขเป็นจริง พิมพ์ "Pair exists" และคืนค่าจาก main function
• มิฉะนั้น 继续เดินทางผ่านอาร์เรย์และสุดท้ายพิมพ์ "Pair does not exist."

สรุป

ในบทความนี้ เราอภิปรายการหาคู่ที่มีผลรวมที่กำหนดในเมทริกซ์หรืออาร์เรย์ 2 มิติ เราอภิปรายวิธี Brute-force และวิธี Efficient ในการแก้ปัญหานี้ เราอภิปรายโปรแกรม C++ เพื่อแก้ปัญหานี้ อย่างไรก็ตาม เราสามารถเขียนโปรแกรมนี้ในภาษาอื่นๆ เช่น C, Java, Python ฯลฯ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์