首页 > 试题广场 >

合法的三角形个数

[编程题]合法的三角形个数
  • 热度指数：1035 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个长度为N的非负整数数组nums，请你计算一下，有多少个三元组代表的边长可以组成三角形
数据范围:


示例1

输入

[2,3,4,4]

输出

4

说明

合法的有4个：
2 3 4(第一个4)
2 3 4(第二个4)
2 4 4
3 4 4
算法知识视频讲解
开通博客
头像 fred-coder
发表于 2022-02-04 15:27:34
三角形两边之和大于第三边，将数组排序，利用二分法找到小于两边之和的第三边个数，相加得到最终的结果; # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # import bise 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 mshentai
发表于 2022-01-16 09:58:55
该题的解法如下： 首先，对各边长进行排序，方便获取三边中最长的边。 然后，进入循环，循环体如下： 由小到大找最长边（循环） 从最长边开始由大到小找次长边（循环） 从次长边开始由大到小找最短边。(循环计数法，或者用二分查找法找上界，然后用计算中间个数） 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 爱唱歌的潜伏者在发呆
发表于 2024-02-26 13:21:24
class Solution { public: int validTriangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end());//数组排序 int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客791853757号
发表于 2022-06-17 15:29:54
public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ret = 0; for (int i = 0; i < n; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客494732号
发表于 2023-05-23 10:00:58
package main import ( "sort" ) /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ func validTriangleNu 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 O_胡萝卜_O
发表于 2022-08-13 15:38:24
class Solution:     def validTriangleNumber(self , nums: List[int]) -> int:   &nbs 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 双指针
上传者：牛客301499号
难度：
3条回答 2002浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号