การนับจำนวนด้านสามเหลี่ยมในอาร์เรย์ใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ตัวเลข arr เป็นอาร์กิวเมนต์แรกและเดียว ภารกิจของฟังก์ชันคือนับจำนวน triplet ที่เลือกจากอาร์เรย์ที่สามารถสร้างสามเหลี่ยมได้ ถ้านำไปเป็นความยาวด้าน

เช่น ถ้าอินพุตคือ:

const arr = [2, 2, 3, 4];

ผลลัพธ์ควรเป็น:

const output = 3;

คำอธิบายผลลัพธ์

Valid combinations:

2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

ตัวอย่าง

โค้ดตัวอย่างด้านล่าง:

const arr = [2, 2, 3, 4];
const countTriangle = (arr = []) => {
  arr.sort((a, b) => a - b);
  let k = 2;
  let count = 0;
  for (let i = 0; i < arr.length - 2; i++) {
    for (let j = i + 1; j < arr.length - 1; j++) {
      k = j + 1;
      while (arr[k] < arr[i] + arr[j]) {
        k += 1;
      }
      count += k - j - 1;
    }
  }
  return count;
};
console.log(countTriangle(arr));

ผลลัพธ์

3

คำอธิบายเพิ่มเติม

เงื่อนไขสามเหลี่ยม: a+b>c, a+c>b, b+c>a สำหรับ sorted array a≤b≤c ต้องการแค่ a+b>c โค้ดใช้ two-pointer technique: fix i,j หา k สุดท้ายที่ a+b>c → count += k-j-1 O(n²) time