ในปัญหานี้ เรามีอาร์เรย์ที่ไม่เรียงลำดับ และเราต้องพิมพ์คู่ทั้งหมดภายในอาร์เรย์นี้ที่มีผลรวมเท่ากัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
Input: array = [12, 13, 20, 5] Output: [12, 13] and [20, 5] have sum 25.
เพื่อแก้ปัญหานี้ เราจะต้องหาคู่ที่มีผลรวมเท่ากัน สำหรับสิ่งนี้เราจะตรวจสอบคู่สำหรับผลรวมเดียวกัน และเพื่อหลีกเลี่ยงคู่ที่ซ้ำกัน เราจะใช้แผนที่นี้
สำหรับสิ่งนี้ เราจำเป็นต้องมีแผนที่สองแผนที่ แผนที่หนึ่งสำหรับเก็บคู่ผลรวมและผลรวม และแผนที่อื่นๆ เพื่อเก็บผลรวมทั้งหมดและคู่ที่สัมพันธ์กัน
ดังนั้น Map1 → คีย์ =คู่; ค่า → ผลรวม
Map2 → คีย์ =ผลรวมจำนวนเต็ม; ค่า → เวกเตอร์ของคู่
ตอนนี้ ให้พิมพ์ค่าทั้งหมดที่มีมูลค่ารวมเท่ากัน
ตัวอย่าง
โปรแกรมเพื่อแสดงตรรกะข้างต้น -
#include <bits/stdc++.h>
using namespace std;
void findEqualSumPairs(int A[], int n){
map<int, vector<pair<int, int> > >map1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pair<int, int> p = make_pair(A[i], A[j]);
map1[A[i] + A[j]].push_back(p);
}
}
for (auto value = map1.begin(); value != map1.end(); value++) {
if (value->second.size() > 1) {
for (int i = 0; i < value->second.size(); i++) {
cout<<"[ "<<value->second[i].first<<", "<<value->second[i].second<<"] ";
}
cout<<"have sum : "<<value->first<<endl;
}
}
}
int main() {
int A[] = { 6, 4, 12, 10, 22,11, 8, 2 };
int n = sizeof(A) / sizeof(A[0]);
cout<<"Pairs with same sum are : \n";
findEqualSumPairs(A, n);
return 0;
} ผลลัพธ์
คู่ที่มีผลรวมเท่ากันคือ −
[ 6, 4] [ 8, 2] have sum : 10 [ 4, 8] [ 10, 2] have sum : 12 [ 6, 8] [ 4, 10] [ 12, 2] have sum : 14 [ 6, 10] [ 4, 12] have sum : 16 [ 6, 12] [ 10, 8] have sum : 18
