### 题目

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:

• The length of the given array won’t exceed 1000.
• The integers in the given array are in the range of [0, 1000].

### 二分查找

第三边 < 2 + 2 = 4

i j k
| | |
2,2,3,4,6,6,7
|
max



二分查找"70"，会指向第二个70。需要将指针前移到第一个70处。

binary search
|
[34,75,96,10,60,70,70,45]
|
修正后的位置


#### 代码

class Solution {
public int triangleNumber(int[] nums) {
int count = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
int max = nums[i] + nums[j];
int searchResult = Arrays.binarySearch(nums, max);
int maxIdx = (searchResult < 0)? - (searchResult + 1) : searchResult;
if (maxIdx < nums.length) {
while (maxIdx > 0 && nums[maxIdx - 1] == nums[maxIdx]) maxIdx--;
}
int diff = maxIdx - (j + 1);
if (diff > 0) count += diff;
}
}
return count;
}
}