# 611. Valid Triangle Number

## 1. Question

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

## 2. Examples

Example 1:

Input: nums = [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


Example 2:

Input: nums = [4,2,3,4]
Output: 4


### 2.1. Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

## 4. Solutions

class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
if (null == nums || nums.length < 3) {
return 0;
}

int res = 0;

for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {

// 暴力算法
//                for (int k = j + 1; k < nums.length; k++) {
//                    if (nums[i] + nums[j] > nums[k]){
//                        res++;
//                    }
//                }

// 二分法
int left = j + 1;
int right = nums.length - 1;
int k = j;

while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[i] + nums[j]) {
k = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
res += k - j;
}
}

return res;
}
}

public class Solutions {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int cnt = 0;
int n = nums.length;

for (int i = n - 1; i > 2; i--) {
int left = 0;
int right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
cnt += right - left;
right--;
} else {
left++;
}
}
}
return cnt;
}
}