Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]Output: 3Explanation:Valid combinations are: 2,3,4 (using the first 2)2,3,4 (using the second 2)2,2,3

 

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

思路：

首先将数组排序。依次取出前两个边的长度。第三条边长度小于前两个边的和。

查找第三条边用二分查找。

int triangleNumber(vector
     
      & a) {      int i,j,k,n,left,right,mid,ans,sum;      ans=0;      sort(a.begin(),a.end());      n=a.size();      for (i=0;i
      
       1)          {            mid=(left+right)/2;            if (a[mid]>=sum) right=mid;            else left=mid;          }          ans+=left-j;        }      return ans;    }
      
     

参考：