Chúng tôi được cung cấp một mảng, giả sử, arr [] các giá trị nguyên có kích thước tương ứng bất kỳ và nhiệm vụ là tính số lượng các cặp phân biệt có sẵn trong một mảng nhất định mà tổng của chúng cũng tồn tại trong cùng một mảng.
Mảng là một loại cấu trúc dữ liệu có thể lưu trữ một tập hợp tuần tự có kích thước cố định của các phần tử cùng kiểu. Mảng được sử dụng để lưu trữ một tập hợp dữ liệu, nhưng thường hữu ích hơn nếu coi một mảng là một tập hợp các biến cùng kiểu.
Những điểm cần nhớ
-
Một cặp sẽ được đếm một lần với các phần tử giống nhau bất kể thứ tự của chúng. Ví dụ:(3,2) và (2,3) sẽ được tính là 1.
-
Nếu có một số xuất hiện nhiều lần trong một mảng thì nó sẽ được coi là chính xác hai lần để tạo thành một cặp. Ví dụ:nếu một mảng có các phần tử là {2, 2, 2, 2} thì cặp đó sẽ là (2,2) và nó sẽ được tính là 1.
Ví dụ
Input − int arr = {6, 4, 10, 14}
Output − count is 2 Giải thích - các cặp có tổng trong một mảng là (6,4) và (10,4) nên số đếm là 2
Input − int arr = {6, 6, 6 ,6, 6, 13}
Output − count is 0 Giải thích - không có cặp nào trong một mảng với tổng trong cùng một mảng. Vì vậy, số đếm là 0.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tạo một mảng, giả sử arr []
-
Tính độ dài của mảng bằng cách sử dụng hàm length () sẽ trả về một giá trị nguyên theo các phần tử trong mảng.
-
Lấy một biến tạm thời sẽ lưu trữ số lượng phần tử.
-
Tạo một biến loại bản đồ, giả sử là mp
-
Bắt đầu vòng lặp cho tôi đến 0 và tôi nhỏ hơn kích thước của một mảng
-
Tạo một bản đồ khác của biến loại cặp, giả sử là par
-
Bắt đầu vòng lặp cho tôi đến 0 và tôi nhỏ hơn kích thước của một mảng
-
Bên trong vòng lặp, bắt đầu một vòng lặp khác với j đến i + 1 và j nhỏ hơn kích thước của một mảng
-
Trong vòng lặp, hãy kiểm tra xem mp [arr [i] + arr [j]]> 0 AND pr [{arr [i], arr [j]}] =0 rồi tăng số lượng lên 1
-
Số tăng par [{arr [i], arr [j]}] lên 1
-
Số tăng par [{arr [j], arr [i]}] lên 1
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#include <iostream>
#include <map>
using namespace std;
// Returns number of pairs in ar[0..n-1] with
// sum equal to 'sum'
int countpairs(int ar[], int n){
// Store counts of all elements in map m
// to find pair (ar[i], sum-ar[i])
// because (ar[i]) + (sum - ar[i]) = sum
map<int, int> mymap;
for (int i = 0; i < n; i++){
mymap[ar[i]]++;
}
// To remove duplicate items we use result map
map<pair<int, int>, int> p;
int result = 0;
// Considering all pairs
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// If sum of current pair exists
if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] ==0){
result++;
}
// Inserting the current pair both ways to avoid
// duplicates.
p[{ ar[i], ar[j] }]++;
p[{ ar[j], ar[i] }]++;
}
}
return result;
}
// main function
int main(){
int ar[] = { 6, 4, 10, 14 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "count is "<<countpairs(ar, n);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is 2