611. Valid Triangle Number
1.Problem
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.Solution
题目的大意是给定一个元素可能存在重复的一维数组，给出其中能组成合法三角形的组合数。
3.Code
//Solution1
//时间复杂度O(N^3),空间复杂度O(logN)(排序导致)
//先对nums数组进行排序，如从大小三条边为 a，b，c，只需判断 a + b > c 成立与否 =》三条边能否构成三角形
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int l = nums.length;
int count = 0;
for ( int i = 0 ; i < l - 2 ; i++ ) {
for ( int j = i + 1 ; j < l - 1 ; j++ ) {
for ( int k = j + 1 ; k < l ; k++ ) {
if ( nums[i] + nums[j] > nums[k]) {
count++;
}
}
}
}
return count;
} }
//Solution2 二分查找
//时间复杂度O(N^2 * log(N))，空间复杂度O(log N)
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int l = nums.length;
int count = 0;
for ( int i = 0 ; i < l - 2 ; i++ ) {
int k = i + 2;
for ( int j = i + 1 ; j < l - 1 && nums[i] != 0 ; j++ ) {
k = binarySearch(k,l - 1,nums,nums[i] + nums[j]);
count += k - j - 1;
}
}
return count;
} public int binarySearch( int start , int end , int[] nums , int target ) {
while ( start <= end ) {
int mid = ( end - start ) / 2 + start;
if ( nums[mid] < target ) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
} }
//Solution3,时间复杂度O(N^2) ,空间复杂度O(lgN)
ime complexity : O(n2)O(n^2)O(n2). Loop of kkk and jjj will be executed O(n2)O(n^2)O(n2) times in total, because, we do not reinitialize the value of kkk for a new value of jjj chosen(for the same iii). Thus the complexity will be O(n^2+n^2)=O(n^2).
Space complexity : O(logn)O(logn)O(logn). Sorting takes O(logn) space.
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int l = nums.length;
int count = 0;
for ( int i = 0 ; i < l - 2 ; i++ ) {
int k = i + 2;
for ( int j = i + 1 ; j < l - 1 && nums[i] != 0 ; j++ ) {
while ( k < l && (nums[i] + nums[j] > nums[k]) ) {
k++;
}
count += k - j - 1;
}
}
return count;
}
}