原题
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例1:
输入： [2,2,3,4] 输出： 3
解释：
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
- 数组长度不超过1000。
- 数组里整数的范围为 [0, 1000]。
解法
思想
三角形的某两边之和必须大于第三边且两边之差小于第三边
方法：
- 暴力：获取所有3元组，判断能否构成三角形
- 动态规划：先给数组排序，任意两个较小边之和必须大于第三边。
对于数组[1,3,4,5,6]，先将最大边指向6，一最小边i指向1，一最小边j指向5，如下图所示。
1+5不大于6，可以将最小边往后移一格。
如图所示，此时3+5大于6，可以组成三角形，而因为数组是排序过的，则最小边再向后移最小两边之和也是大于第三边的，所以此时可以把总数加上j-i，然后把i还原回数组头部，j向前移一格
重复之前步骤，1+4不大于6，i向后移一格，3+4大于6，总数加上j-i。
代码
- 暴力
class Solution {
public int triangleNumber(int[] nums) {
int count = 0;
for(int i = 0;i<nums.length-2;i++){
for(int j = i+1;j<nums.length-1;j++){
for(int n = j+1;n<nums.length;n++){
if(nums[i]+nums[j]>nums[n]&&Math.abs(nums[i]-nums[j])<nums[n]) count++;
}
}
}
return count;
}
}
- 动态规划
class Solution {
public int triangleNumber(int[] nums) {
int count = 0;
Arrays.sort(nums);
for(int n = nums.length-1;n>=2;n--){
int i = 0;
int j = n-1;
while(i<j){
if(nums[i]+nums[j]>nums[n]) {
count+=(j-i);
j--;
}else{
i++;
}
}
}
return count;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode611-%e6%9c%89%e6%95%88%e4%b8%89%e8%a7%92%e5%bd%a2%e7%9a%84%e4%b8%aa%e6%95%b0/
