class Solution {
public:
    int binarySearch(vector<int>& nums, int target, int left){
        // find the number that smaller than a + b
        // for example: 2 2 3 3 4 4
        // final:             r l
        // return (l - left) number are smaller than a + b
        int l = left;
        int r = nums.size() - 1;
        int mid;

        while(l <= r){
            mid = l + (r - l) / 2;

            if(nums[mid] == target){
                r = mid - 1;
            } else if(nums[mid] > target){
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l - left;
    }

    int triangleNumber(vector<int>& nums) {
        int n = nums.size() - 1;
        int ans = 0;

        sort(nums.begin(), nums.end());

        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                int sum = nums[i] + nums[j];
                ans += binarySearch(nums, sum, j+1);
            }
        }

        return ans;
    }
};