给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
解1
暴力求解，时间复杂度n^3
public int triangleNumber(int[] nums) {
int len = nums.length,res = 0;
if(len<3)
return 0;
Arrays.sort(nums);
int a,b,c;
for(int i=0;i<len-2;i++){
a = nums[i];
for(int j=i+1;j<len-1;j++){
b = nums[j];
for(int k = j+1;k<len;k++){
c = nums[k];
if(a+b>c)
res++;
else
break;
}
}
}
return res;
}
解2
时间复杂度n^2。从后往前遍历数组，每次遍历时对该位置的左边的数组使用双指针的思想，从头和尾做一次遍历。
public int triangleNumber(int[] nums) {
int len = nums.length,res = 0;
if(len<3)
return 0;
Arrays.sort(nums);
int left,right;
for(int i=len-1;i>=2;i--){
left = 0;
right = i-1;
while(left<right){
if(nums[left]+nums[right]>nums[i]){
res += right-left;
right--;
}else{
left++;
}
}
}
return res;
}
