Số bộ ba tạo thành tam giác (Valid Triangle Number) trong C++

Cho mảng số nguyên không âm, đếm số bộ ba chỉ số (i, j, k) sao cho ba cạnh tương ứng tạo thành tam giác (thỏa mãn bất đẳng thức tam giác).

Ví dụ: [2,2,3,4] → 3 bộ ba: (2,3,4) (2 lần), (2,2,3).

Thuật toán (Sắp xếp + Hai con trỏ)

1. Sắp xếp mảng tăng dần.
2. Duyệt i từ cuối về 0 (cạnh lớn nhất).
3. Đặt left=0, right=i-1.
4. Nếu nums[left] + nums[right] > nums[i] → tất cả cặp từ left đến right-1 với right đều hợp lệ → cộng right-left, giảm right.
5. Ngược lại tăng left.

Mã nguồn C++

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

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ret = 0, n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = n-1; i >= 0; i--) {
            int left = 0, right = i-1;
            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;
}

Đầu vào / Đầu ra

Input: [2,2,3,4]

Output: 3