มี input a เป็น array ที่มีขนาดเป็น n จงหาและนับจำนวน triplets ของ index (d, e, f) ใน array a ที่ตรงตาม 0 <= d < e < f < n และค่าต่อไปนี้เป็นจริง
a[d] + a[e] > a[f]
a[e] + a[f] > a[d]
a[f] + a[d] > a[e]
ข้อจำกัด
- ใช้ time complexity สูงสุดที่ O(n^2)
- ใช้ space complexity สูงสุดที่ O(n) ไม่รวม input
แซมเปิ้ล input [10, 2, 5, 1, 8, 12]
แซมเปิ้ล output 4
ตัวอย่าง index ของ triplets ที่ตรงตามโจทย์
(0, 2, 4), (0, 2, 5), (0, 4, 5), (2, 4, 5)
ไม่ใช่ที่สอบอะนะ แค่ตัวอย่างจากที่เดียวกัน
โจทย์นี้ทำเองได้แค่ O(n^3) ไปดูเฉลยแล้วทำ O(n^2) ได้จริงๆ
ที่โดนให้ทำมีทั้งยากกว่านี้และง่ายกว่านี้ แต่เวลาจำกัดกว่าเยอะ เลยทำได้แค่ไม่กี่ข้อ มั่นใจว่าไม่ผ่านชัวร์