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.
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
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length, count = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int lastValidIdx = binarySearch(j, n - 1, nums[i] + nums[j], nums);
// System.out.println(i + "\t" + j + "\t" + lastValidIdx);
count += lastValidIdx - j;
}
}
return count;
}
private int binarySearch(int lt, int rt, int target, int[] nums) {
int idx = lt;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (nums[mid] >= target)
rt = mid - 1;
else {
idx = mid;
lt = mid + 1;
}
}
return idx;
}
}class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] <= nums[k])
break;
count++;
}
}
}
return count;
}
}class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int i = 0, n = nums.length, count = 0;
while (i < n && nums[i] == 0)
i++;
for (; i < n - 2; i++) {
int k = i + 2;
for (int j = i + 1; j < n - 1; j++) {
while (k < n && nums[i] + nums[j] > nums[k])
k++;
count += k - j - 1;
}
}
return count;
}
private int binarySearch(int lt, int rt, int target, int[] nums) {
int idx = lt;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (nums[mid] >= target)
rt = mid - 1;
else {
idx = mid;
lt = mid + 1;
}
}
return idx;
}
}