Đếm số tam giác có thể tạo thành từ mảng độ dài cạnh C++

Cho mảng chứa độ dài các cạnh. Đếm số bộ ba (i,j,k) với i cạnh còn lại).

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 4, 5}
• Output: 1
• Giải thích: Chỉ (2,4,5): 2+4>5, 4+5>2, 2+5>4.

Ví dụ 2:

• Input: arr = {4, 5, 6, 3, 2}
• Output: 7
• Giải thích: (4,5,6), (4,5,2), (4,5,3), (4,3,2), (5,6,3), (5,6,2) - cần kiểm tra lại 7 bộ ba.

Tối ưu quan trọng: Sắp xếp mảng trước

Nếu mảng đã sắp xếp: a ≤ b ≤ c. Chỉ cần kiểm tra a + b > c (hai điều kiện còn lại tự động thỏa mãn).

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

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

int countTriangles(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[i] + arr[k] > arr[j] &&
                    arr[k] + arr[j] > arr[i]) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 5, 3, 6, 8, 10};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "So tam giac co the tao: " << countTriangles(Arr, len);
    return 0;
}

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

So tam giac co the tao: 8

Tối ưu hóa O(n²) - Two Pointers sau khi sắp xếp

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

int countTrianglesOptimized(int arr[], int n) {
    sort(arr, arr + n);
    int count = 0;
    
    // Fix c là cạnh lớn nhất (index k)
    for (int k = n - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (arr[i] + arr[j] > arr[k]) {
                // Tất cả cặp từ i đến j-1 với j đều thỏa mãn
                count += (j - i);
                j--;
            } else {
                i++;
            }
        }
    }
    return count;
}

Độ phức tạp

Lưu ý

• Sắp xếp mảng là bước quan trọng để áp dụng two pointers.
• Khi arr[i] + arr[j] > arr[k], vì mảng tăng dần, mọi chỉ số từ i đến j-1 cùng với j đều thỏa mãn → cộng (j-i) vào count.