โปรแกรมนับ triplet ที่เป็นสามเหลี่ยมได้ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ตัวเลข ต้องการนับจำนวน triplet ที่สามารถเป็นด้านของสามเหลี่ยมได้ (Triangle Inequality: a + b > c, a + c > b, b + c > a)

ตัวอย่าง

Input: [2,2,3,4]

Output: 3

คำอธิบาย: [2,3,4] (ใช้ 2 ตัวแรก), [2,3,4] (ใช้ 2 ตัวที่สอง), [2,2,3]

แนวทางแก้ปัญหา (Two Pointers หลังเรียงลำดับ)

1. เรียงอาร์เรย์จากน้อยไปมาก
2. กำหนด c เป็นด้านยาวสุด (วนจากท้ายไปหน้า)
3. ใช้ two pointers: left=0, right=c-1
4. ถ้า nums[left] + nums[right] > nums[c] → ทุกคู่ระหว่าง left..right-1 กับ right กับ c เป็นสามเหลี่ยมได้ → เพิ่ม (right-left) แล้ว right--
5. มิฉะนั้น left++

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

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

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        for (int i = n - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
};

int main() {
    vector<int> v = {2,2,3,4};
    Solution ob;
    cout << ob.triangleNumber(v);
    return 0;
}

ผลลัพธ์

3

ความถูกต้อง

หลังเรียงแล้ว: a ≤ b ≤ c

เงื่อนไขสามเหลี่ยม: a + b > c (เพียงพอ เพราะ a+c>b และ b+c>a เป็นจริงอัตโนมัติ)

Two pointers หา (a,b) ที่ a+b>c ได้ใน O(N) ต่อ c คงที่

ความซับซ้อน

• เวลา: O(N²) — เรียง O(N log N) + two pointers O(N²)
• พื้นที่: O(1) หรือ O(log N) สำหรับ sorting stack

การประยุกต์ใช้

ปัญหานี้เป็น LeetCode 611 "Valid Triangle Number" — คลาสสิกของ two pointers pattern