​LeetCode刷题实战611：有效三角形的个数

示例 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

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        //先进行排序 为二分查找建立条件
        sort(nums.begin(),nums.end());
        for(int i = 0; i < n - 2; ++i){
            for(int j = i + 1; j < n - 1; ++j){
                //固定两条边
                int sum = nums[i]+nums[j];
                //二分查找第三条符合得边 发现了二分查找的一个边界问题 right能否被取到是关键是<= 还是<
                int left = j + 1;
                int right = n - 1;
                while(left <= right){
                    int mid = (right-left)/2 + left;
                    if(nums[mid] < sum){
                        left = mid + 1;
                    }else{
                        right = mid - 1 ;
                    }
                }
                //判断边界 如果右边界都满足那么左边界到右边界上的每一个元素都满足
                if(nums[right]<sum){
                    res = res + right - j;
                }
            }
        }
        return res;
    }
  
};