博客

• Question
  
  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

• 思路
  
  能做三角形的边要满足

  1. 两边之和大于第三边。
  2. 两边之差小于第三边。

• 如果三个数满足: a<=b<=c;
  
  那么只要这三个数满足 a+b>c , 就必然满足 c-b < a 、c-a < b 和 b-a < c.
  
  这三个数就是符合条件的一组数。
  
  在对数组排序后， 从前面取出两个数 a, b， 用二分查找在之后找到满足a+b > c的 最大的 c。

• 代码如下：

int triangleNumber(vector<int>& nums) {
    int ret = 0;
    if (nums.size() > 2) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i++) {
            int j = i + 1;
            while (j < nums.size() - 1) {
                int sum=nums[i] + nums[j];
                int left=j+1, right=nums.size();   //right不能取nums.size()-1, 因为left=rigth+1 并且nums[left] 和nums[right] 同时满足条件时时，就无法取到right了 
                if(sum>nums[left]){
                    while (left +1 < right ) {
                        int mid=(left+right)/2;

                        if(nums[mid]>=sum) right=mid;
                        else left=mid;
                    }
                    ret+=(left-j);
                } 
                j++;
            }
        }
    }
    return ret;
}