611. 有效三角形的个数

判断三条边能组成三角形的条件为：

1. 任意两边之和大于第三边，任意两边之差小于第三边。
2. 三条边长从小到大为 a、b、c，当且仅当 a + b > c 这三条边能组成三角形。

二分查找

• 首先对数组排序。
• 固定最短的两条边，二分查找最后一个小于两边之和的位置。可以求得固定两条边长之和满足条件的结果。枚举结束后，总和就是答案。
• 时间复杂度为 O(n^2logn)

  class Solution {
    public int triangleNumber(int[] nums) {
        if(nums==null || nums.length == 0){
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        int n = nums.length;
        for(int i = 0 ; i < n-2 ; i++){
            for(int j = i+1 ; j < n-1 ; j++){
                int left = j+1;
                int right = n-1;
                int add = nums[i] + nums[j];
                while(left < right){
                    int mid = (left + right + 1)>>>1;
                    if(nums[mid] < add){
                        left = mid;
                    }else{
                        right = mid - 1;
                    }
                }
                if(nums[right] < add){
                    res += (right - j);
                }
            }
        }
        return res;
    }   
  }