Cho ma trận và giá trị SUM, kiểm tra có tồn tại cặp phần tử nào có tổng = SUM không. Ví dụ:
Input: matrix 4x4, SUM = 20 → Pair exists (9+11) Input: matrix 4x4, SUM = 13 → Pair does not exist
Cách vét cạn O((NM)²)
Kiểm tra mọi cặp.
Cách hiệu quả: Hash Set O(N×M)
Duyệt ma trận, với mỗi phần tử x kiểm tra SUM - x đã có trong set chưa. Nếu có → tồn tại cặp. Thêm x vào set.
Ví dụ
#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<int> 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;
}
hash.insert(matrix[i][j]);
}
cout << "Pair does not exist." << endl;
return 0;
}
Kết quả
Pair does not exist.
Kết luận
Kiểm tra tồn tại cặp có tổng cho trước trong ma trận dùng Hash Set O(N×M). Code C++ mẫu.