611.有效三角形的个数

611. 有效三角形的个数

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

示例 1:

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

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

C++

// 法一: 二重循环+二分
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        // nums[i] <= nums[j] <= nums[k] 
        // 所以 nums[i] < nums[j] + nums[k];  nums[j] < nums[k] + nums[i]
        // 二分找第一个 >= nums[i] + nums[j] 的 nums[k], 若能找到，res += k - j - 1  
        // 若找不到，res += n - j - 1 
        int res = 0;
        for(int i = 0; i < n - 2; i ++){
            for(int j = i + 1; j < n - 1; j ++){
                auto it = lower_bound(nums.begin() + j + 1, nums.end(), nums[i] + nums[j]);
                if(it != nums.end()){
                    res += it - nums.begin() - j - 1;
                }else res += n - j - 1;
            }
        }
        return res;
    }
};






//法二： 双指针优化, k在j里不重置
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int k = i;
            for (int j = i + 1; j < n; ++j) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) ++k;
                res += max(k - j, 0);
            }
        }
        return res;
    }
};