611-有效三角形的个数

611. 有效三角形的个数

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

method

构成三角形的条件

a + b > c
a + c > b
b + c > a

如果对数组排序，保证a<b<c，这样就只需要满足c<a+b就可以了

二重枚举nums[i]和nums[j]，然后在[j+1,n-1]这个区间中找小于nums[i]+nums[j]的最大数

int triangleNumber(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int target = nums[i] + nums[j];
            int l = j + 1, r = n - 1;   // 注意这里l会越界
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (nums[mid] < target) l = mid;
                else r = mid - 1; 
            }
            if (nums[r] < target) res += (r - j);   // 所以这里要用r
        }
    }
    return res;
}