原题
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例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/
相关推荐
-
leetcode1162-地图分析
原题 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域...
-
leetcode1144-递减元素使数组呈锯齿状
原题 给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。 如果符合下列情况之一，则数组 A 就是 锯齿数组： 每个偶数索引对应的元素都大于相邻的元...
-
leetcode189-旋转数组
原题 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4...
-
leetcode387-字符串中的第一个唯一字符
原题 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"...
-
leetcode542-01矩阵
原题 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例1: 输入: 0 0 0 0 1 0 0 0 0 输出: 0 0 ...
-
leetcode16-最接近的三数之和
原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存...
-
leetcode707-设计链表
原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用...
-
剑指offer50-第一个只出现一次的字符
原题（来源Leetcode） 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s...
-
leetcode1095-山脉数组中查找目标值
原题 （这是一个 交互式问题 ） 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in...
-
leetcode205-同构字符串
原题 给定两个字符串 s 和 t，判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换，同时保留字符的顺...