(C++)有效三角形的个数--双指针法

简介: (C++)有效三角形的个数--双指针法

个人主页:Lei宝啊

愿所有美好如期而遇


算法原理

双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针。我们一般判断三角形,要将三条边都判断一次,两边和大于第三边才能构成三角形,但是我们可以发现,当我们将这三条边大小从小到大排序后,小的两条边和大于第三边,那么就一定能构成三角形,这道题我们就可以这样判断,简化一下我们的代码。

我们先将数组进行排序,然后从右边开始固定一条边,接着定义left,right,left赋值0,right赋值固定边下标-1,之后我们判断left和right这两条边之和是否大于固定的边,如果大于,那么就能构成right-left个数的三角形,如果小于,那么left++。固定边算过后,将这条边下标--,重复上述步骤,直到就剩两条边,也就是下标等于1,我们结束。

图示

以此类推,不再往下画了。

代码

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int count = 0;
        for(int i=nums.size()-1; i>1; i--)
        {
            int left = 0;
            int right = i - 1;
            while(right != left)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    count += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return count;
    }
};


目录
相关文章
|
Ubuntu
【报错】解决Ubuntu环境下VsCode无法输入中文
【报错】解决Ubuntu环境下VsCode无法输入中文
669 0
|
应用服务中间件 网络安全 nginx
运维专题.Docker+Nginx服务器的SSL证书安装
运维专题.Docker+Nginx服务器的SSL证书安装
759 3
|
7月前
|
存储 人工智能 运维
阿里云操作系统控制台——解决服务器磁盘I/O故障
阿里云操作系统控制台——解决服务器磁盘I/O故障
226 12
|
算法 Serverless 知识图谱
0基础理解ECC并做题-攻防世界easy-ECC理解
0基础理解ECC并做题-攻防世界easy-ECC理解
|
JSON 前端开发 JavaScript
成功解决:[object Object]
这篇文章讨论了在JavaScript中打印对象时出现的"[object Object]"问题的原因,并提供了使用`JSON.stringify()`方法将对象转换为字符串以便于打印和调试的解决方案。
成功解决:[object Object]
|
12月前
|
缓存 Ubuntu 网络协议
ubuntu ifconfig命令找不到
通过上述指导,无论你是面临 `ifconfig`命令缺失的困惑,还是希望深入了解Ubuntu系统下的网络管理技巧,都能找到针对性的解决方案,进一步提升你的系统管理能力。
422 2
|
10月前
|
前端开发 JavaScript API
提取网页所有链接免费API接口教程
此API用于提取指定网页内的所有链接信息并进行分类,支持POST和GET请求方式。需提供用户ID、KEY及目标网址等参数,可选指定访问节点。返回结果包括状态码、信息提示及各类链接集合,如图片、视频、文档等。示例中展示了请求格式与返回数据结构。
|
12月前
|
SQL 存储 关系型数据库
SQL判断CHAR类型字段不为空的方法与技巧
在SQL查询中,判断一个CHAR类型字段是否不为空是一个常见的需求
|
小程序 前端开发 JavaScript
微信小程序结合PWA技术,提供离线访问、后台运行、桌面图标及原生体验,增强应用性能与用户交互。
微信小程序结合PWA技术,提供离线访问、后台运行、桌面图标及原生体验,增强应用性能与用户交互。开发者运用Service Worker等实现资源缓存与实时推送,利用Web App Manifest添加快捷方式至桌面,通过CSS3和JavaScript打造流畅动画与手势操作,需注意兼容性与性能优化,为用户创造更佳体验。
522 0
|
前端开发 区块链 数据安全/隐私保护
web3 的身份验证之以太坊签名消息
如果参与过以太坊 DApp 相关的开发,可能遇到过要求签名一条消息或一条数据以验证自己(以及哈希地址)。本文将讨论以太坊签名数据的基础知识。
2123 0
web3 的身份验证之以太坊签名消息