原题
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例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/
相关推荐
-
leetcode453-最小移动次数使数组元素相等
原题 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只...
-
leetcode111-二叉树的最小深度
原题 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul...
-
leetcode173-二叉搜索树迭代器
原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator...
-
蓝桥杯试题-小数第n位
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。 如果我们把有限小数的末尾加上无限多个...
-
leetcode912-排序数组
原题 给定一个整数数组 nums，将该数组升序排列。 示例 1: 输入： [5,2,3,1] 输出： [1,2,3,5] 示例 2: 输入： [5,1,1,2,0,0] 输出： [...
-
leetcode1103-分糖果II
原题 排排坐，分糖果。 我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类...
-
leetcode313-超级丑数
原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入： n = 12, primes = [2...
-
leetcode733-图像渲染
原题 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一...
-
leetcode13-罗马数字转整数
原题 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2...
-
leetcode128-最长连续序列
原题 给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长...