Đếm bộ ba (triplets) có một số bằng tổng hai số kia C++

Cho mảng Arr[] độ dài n. Đếm số bộ ba (i,j,k) với i

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 2, 3, 4}, N = 5
• Output: 4
• Giải thích: (1,2,3)×2 (do có 2 số 2), (1,3,4), (2,2,4).

Ví dụ 2:

• Input: arr = {2, 2, 2, 2, 2}, N = 5
• Output: 0
• Giải thích: 2+2=4 ≠ 2.

Mã nguồn C++ (Vét cạn O(n³))

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

int countTriplets(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] == arr[k] ||
                    arr[j] + arr[k] == arr[i] ||
                    arr[k] + arr[i] == arr[j]) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 2, 3, 4};
    int N = 5;
    cout << "So bo ba: " << countTriplets(Arr, N);
    return 0;
}

Kết quả chạy chương trình

So bo ba: 4

Tối ưu hóa O(n²) - Sử dụng Hash Set / Two Pointers

Sắp xếp mảng. Với mỗi cặp (i,j), tìm target = arr[i]+arr[j] bằng binary search trong phần còn lại.

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

int countTripletsOptimized(int arr[], int n) {
    sort(arr, arr + n);
    int count = 0;
    
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            int sum = arr[i] + arr[j];
            // Binary search sum trong [j+1, n-1]
            if (binary_search(arr + j + 1, arr + n, sum)) {
                // Đếm số lần xuất hiện của sum
                auto range = equal_range(arr + j + 1, arr + n, sum);
                count += range.second - range.first;
            }
        }
    }
    return count;
}

Độ phức tạp