优选算法|【双指针】|611.有效三角形的个数

简介: 优选算法|【双指针】|611.有效三角形的个数

题目描述

611. 有效三角形的个数

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]

输出: 3

解释:有效的组合是:

2,3,4 (使用第一个 2)

2,3,4 (使用第二个 2)

2,2,3


示例 2:

输入: nums = [4,2,3,4]

输出: 4

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

代码

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        int n=nums.size();//数组大小
         int num=0;//统计三角形个数
         sort(nums.begin(),nums.end());//排序
         for(int i=n-1;i>0;i--)
         {
             int left=0;
             int right=i-1;
             while(left<=right)
             {
                 //排好序后只要比他小的两个数,相加大于大的那个数,就可以组成三角形
                 if(nums[left]+nums[right]>nums[i])
                 {
                     num+=right-left;
                     right--;
                 }
                 else 
                 {
                     left++;
                 }
             }
         }
    return num;
    }
    
};
相关文章
|
10天前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
22小时前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
10天前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
10天前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
10天前
|
机器学习/深度学习 算法 测试技术
【算法优选】 动态规划之子数组、子串系列——壹
【算法优选】 动态规划之子数组、子串系列——壹
|
10天前
|
算法
【算法优选】 动态规划之简单多状态dp问题——贰
【算法优选】 动态规划之简单多状态dp问题——贰
|
21天前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
22天前
|
算法
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
|
22天前
|
算法 C++
【优选算法】——滑动窗口——3. 无重复字符的最长子串
【优选算法】——滑动窗口——3. 无重复字符的最长子串
|
1天前
|
算法 安全
基于龙格库塔算法的SIR病毒扩散预测matlab仿真
该程序使用龙格库塔算法实现SIR模型预测病毒扩散,输出易感、感染和康复人群曲线。在MATLAB2022a中运行显示预测结果。核心代码设置时间区间、参数,并定义微分方程组,通过Runge-Kutta方法求解。SIR模型描述三类人群动态变化,常微分方程组刻画相互转化。模型用于预测疫情趋势,支持公共卫生决策,但也存在局限性,如忽略空间结构和人口异质性。