611. 有效三角形的个数

设 a < b < c, 要使a,b,c构成有效三角形需满足 c < a + b, b - a < c, c - a < b, c - b < a

又有：c > b > b - a, c < a + b => c - a < b && c - b < a ,所以只需满足c < a + b 即可。

对nums数组进行排序，先确定a(i)和b(j)，再二分c的边界k, 则j + 1 -- k 都是满足条件的。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        for(int i = 0; i < n - 2; ++i){
            for(int j = i + 1; j < n - 1; ++j){
                int a = nums[i], b = nums[j];
                int rlimit = a + b; 
                int l = j + 1, r = n - 1;
                while(l < r){
                    int mid = l + (r - l + 1) / 2;
                    if(nums[mid] < rlimit)l = mid;
                    else r = mid - 1;
                }
                if(nums[l] < rlimit)ans += r - j;
            }
        }
        // b - a < c < a + b
        return ans;
    }
};

LC611-有效三角形的个数