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].
reference -- https://leetcode.com/problems/valid-triangle-number/solution/
Idea: it is not like permutation problem(for each position, there are many cases to fill in), because we choose some elements from the array.
sort: to check only one case a+b >c instead of three of them
a +b > c and sorting the array
accepted solution 1: binary search
class Solution {
int res = 0;
public int binarySearch(int[] nums, int left, int right, int target){//[]
while(right >= left && right < nums.length ){//stop comdition is right >= left: there is onl one element
int mid = (right - left)/2 + left;
if(nums[mid] >= target){
right = mid -1;
}else {
left = mid + 1;
}
}
return left;// it is on the right of the number we want: real target, left(index)
}
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for(int i = 0 ; i <= n-3 ; i++){
int a = nums[i];
for(int j = i+1 ; j <= n-2 ; j++){
int b = nums[j];
//System.out.println(j+1);
int index = binarySearch(nums,j+1,n-1, a+b ); //[]// find the largest element smaller than a+b
//System.out.println(index);
//System.out.println(nums[index]);
res = res + index - j-1; //why - 1??
}
}
return res;
}
}
Accepted solution 2 -- O(n^2)
class Solution {
public int triangleNumber(int[] nums) {
int res = 0;
//int n = nums.length;
Arrays.sort(nums);
for(int i = 0; i < nums.length-2; i++){
if(nums[i] == 0) continue;
int k = i + 2; // why here
if(nums[k] == 0) continue;
for(int j = i+1 ; j<nums.length-1; j++){
if(nums[j] == 0) continue;
while(k < nums.length && nums[k]< nums[i]+nums[j] && nums[k]!=0){
k++;// move k
}
res = res + k - j -1;
}
}
return res;
}
}
traverse k and j only n^2 -> square time complexixity