Chương trình đếm số bộ ba tam giác hợp lệ trong C++

Giả sử có một mảng số, ta phải tìm số bộ ba chọn từ mảng có thể tạo thành tam giác nếu lấy chúng làm độ dài ba cạnh. Vì vậy nếu đầu vào là [2,2,3,4], kết quả sẽ là 3 vì có ba bộ ba [2,3,4] dùng 2 đầu tiên, [2,3,4] dùng 2 thứ hai, và [2,2,3].

Để giải quyết, ta làm theo các bước sau:

• ret := 0, n := kích thước nums, sắp xếp nums
• với i từ n-1 xuống 0
  • right := i-1, left := 0
  • khi left < right
    • sum := nums[left] + nums[right]
    • nếu sum > nums[i], tăng ret thêm right-left, giảm right 1, ngược lại tăng left 1
• trả về ret

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#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;
}

Đầu vào

[2,2,3,4]

Đầu ra

3