leetcode611. 有效三角形的个数

分析

三角形两边之和大于第三边，两边只差小于第三边，将数组排序只后，必有a<b<c,则b+c>a,a+c>b肯定成立，那么只要保证a+b>c即可。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        int ans=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;
                while(l<r){//二分
                    int mid=(l+r)>>1;
                    if(nums[mid]==target)r=mid;
                    else if(nums[mid]>target)r=mid;
                    else l=mid+1;
                }
                ans+=l-j-1;
            }
        }
        return ans;
    }
};