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: 3

Explanation:

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<int>& a) {

      int i,j,k,n,left,right,mid,ans,sum;

      ans=;

      sort(a.begin(),a.end());

      n=a.size();

      for (i=;i<n;i++)

        for (j=i+;j<n;j++)

        {

          sum=a[i]+a[j];

          left=j;right=n;

          while (right-left>)

          {

            mid=(left+right)/;

            if (a[mid]>=sum) right=mid;

            else left=mid;

          }

          ans+=left-j;

        }

      return ans;

    }

参考：

https://leetcode.com/lympanda/