นับจำนวน Triplet ที่สร้างสามเหลี่ยมได้ใน C++

ให้อาร์เรย์จำนวนเต็มบวกหรือศูนย์ นับจำนวน triplet ที่เลือกมาสามารถสร้างสามเหลี่ยมได้ (ผลรวมของด้านสองด้านมากกว่าด้านที่สาม)

ตัวอย่าง: [2,2,3,4] → 3 triplet คือ [2,3,4] (ใช้ 2 ตัวแรก), [2,3,4] (ใช้ 2 ตัวที่สอง), [2,2,3]

วิธีแก้ปัญหา (Sort + Two Pointers)

1. เรียงอาร์เรย์ nums จากน้อยไปมาก
2. กำหนด ret = 0, n = ขนาด nums
3. วน i จาก n-1 ลง 0:
   • right = i-1, left = 0
   • while left < right:
     • sum = nums[left] + nums[right]
     • ถ้า sum > nums[i]: ret += right - left, right--
     • มิฉะนั้น: left++
4. คืนค่า ret

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

#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 >= 0; i--) {
            int right = i - 1;
            int left = 0;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > 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;
}

Input

[2,2,3,4]

Output

3