611. Valid Triangle Number
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
错解
刷题刷了一段时间了,凭借直觉,直接递归来求,发现在测试用例174时超时。先贴上超时代码.
public class Solution {
int count = 0;
public int triangleNumber(int[] nums) {
find(nums,0,new ArrayList<Integer>());
return count;
}
public void find(int[] nums, int pos, ArrayList<Integer> arrayList){
if(arrayList.size() == 3){
ArrayList<Integer> list = new ArrayList<>(arrayList);
Collections.sort(list);
if(list.get(0) + list.get(1) > list.get(2)){
count++;
}
return;
}
for(int i = pos; i < nums.length; i++){
arrayList.add(nums[i]);
find(nums,i+1,arrayList);
arrayList.remove(arrayList.size()-1);
}
}
}
正解
思路:为了判断是否满足三角形,需要判断两边之和是否大于第三边。先将整个数组排序,设定三个指针,l,r,p。从后往前遍历,p是末尾指针,r是末尾指针的前一位,l从0开始,若nums[l] + nums[r] > nums[i]
,则r-l
范围的都满足条件,因为数组已经从小到大排序,所以若nums[l]符合条件,那么nums[l…r-1]也符合条件。若不符合nums[l] + nums[r] > nums[i]
,则l++
。时间复杂度为O(n^2)。
public class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count = 0;
for(int i = nums.length-1; i >= 2; i--){
int l = 0;
int r = i-1;
while(l < r){
if(nums[l] + nums[r] > nums[i]){
count = count + (r - l);
r--;
}else{
l++;
}
}
}
return count;
}
}