Mình xin chia sẻ lời giải bài này như sau:

• Đầu tiên ta nhận thấy rằng, việc sắp xếp lại mảng \(a\) đã cho không làm ảnh hưởng đến kết quả bài toán, vì dù sắp xếp thế nào đi chăng nữa thì ta vẫn tìm được \(3\) chỉ số \((i,j,k)\) thoả mãn yêu cầu bài toán.

• Vậy chúng ta sắp xếp lại có ý nghĩa gì ? Thực ra việc này sẽ giúp ta dễ dàng tìm kiếm nhị phân, làm giảm độ phức tạp của bài toán.

Ta có nhận xét như sau:

• Vì mảng \(a\) đã được sắp xếp, nên ta có: \(a[1]<=a[2]<=...<=a[n]\). Khi đó, xét một bộ \(1\le i<j<k\le n\) bất kì, thì ta đã có sẵn hai bất đẳng thức sau:

Đó là:

\(\left\{\begin{matrix} a[i]+a[k]>a[j] \\ a[j]+a[k]>a[i]\end{matrix}\right.\), (vì \(0<a[i]<=a[j]<=a[k]\))

Và để bộ số \((a[i],a[j],a[k])\) là ba cạnh của tam giác, thì ta chỉ việc kiểm tra xem \(a[i]+a[j]> a[k]\) hay không ?

Và để đếm xem có bao nhiêu bộ số thoả mãn như vậy, ta làm như sau:

Bước 1: Ta đi xét tất cả các cặp \(1\le i<j<n-1\). Gọi \(sum(i,j)=a[i]+a[j]\).

Bước 2: Chúng ta sẽ dùng tìm kiếm nhị phân trong đoạn \([j+1,n]\) để đếm xem có bao nhiêu chỉ số \(k\in [j+1,n]\) thoả mãn \(sum(i,j)>a[k]\) là xong.

Độ phức tạp của bài toán này là : \(O(n^2.log(n))\)

Các bạn có thể tham khảo code của mình tại đây: Link