当前位置: 首页 > news >正文

【双指针】Leetcode 有效三角形的个数

题目解析

611. 有效三角形的个数
在这里插入图片描述


算法讲解

回顾知识:任意两数之和大于第三数就可以构成三角形

算法 1:暴力枚举

int triangleNumber(vector<int>& nums) 
{// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候,统计答案if (nums[i] + nums[j] > nums[k])ret++;} }}return ret;}

我们通过枚举每三个没有使用的数字,但是这样加上sort函数的时间,时间复杂度太高

算法 2:双指针

我们先确定一个最大数,然后在这个最大数的左边的区间寻找有效三角形
在这里插入图片描述

  • 如果现在的左右指针的值加起来已经 > 每一次确定的最大值:那么现在的left指针已经不需要移动了,因为当前这个数组已经是经过排序的了,所以当前的left满足条件,left右边的数字也满足条件,此时[left, right]区间的有效三角形的个数就是right - left
  • 如果现在左右指针的值讲起来 <= 每一次确定的最大值:那么就需要将left++,在新的[left, right]区间中寻找有效三角形个数,left++的道理同上述

代码编写

class Solution {
public:int triangleNumber(vector<int>& nums) {//先排序sort(nums.begin(), nums.end());//两数之和 > 第三数int ret = 0;int n = nums.size();for(int i = n - 1; i >= 2; i--){int left = 0;int right = i - 1;//现在nums[i] 就是最大的值,在最大值左边的有序区间里面寻找有效三角形while(left < right){if(nums[left] + nums[right] > nums[i]) {ret += (right - left);right--;  }else left++;}}return ret;}
};

相关文章:

【双指针】Leetcode 有效三角形的个数

题目解析 611. 有效三角形的个数 算法讲解 回顾知识&#xff1a;任意两数之和大于第三数就可以构成三角形 算法 1&#xff1a;暴力枚举 int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n nums.size(), ret 0;// 2. 从…...

python项目练习——4.手写数字识别

使用Python和Scikit-learn库进行机器学习模型训练的项目——手写数字识别。 项目分析&#xff1a; 数据准备&#xff1a;使用公开数据集&#xff08;如MNIST&#xff09;作为训练和测试数据。数据预处理&#xff1a;对图像数据进行归一化、展平等操作&#xff0c;以便输入到机…...

【目标检测】NMS算法的理论讲解

将NMS就必须先讲IOU&#xff0c; IOU就是交并比&#xff0c;两个检测框的交集除以两个检测框的并集就是IOU 为什么要做NMS操作&#xff0c;因为要去除同一个物体的多的冗余检测框 那么NMS算法是如何做的呢&#xff1f; 以上是算法的流程图 下面讲解算法的流程 首先输入是预…...

3-iperf3 使用什么工具可以检测网络带宽、延迟和数据包丢失率等网络性能参数呢?

(1)iperf3简介 1.iperf3简介 2.用途&#xff08;特点&#xff09; 3.下载iperf3地址 &#xff08;2&#xff09;实战 1.iperf3参数 &#xff08;1&#xff09;通用参数&#xff08;客户端和服务器端都是适用的&#xff09; &#xff08;2&#xff09;客户端参数 实验1&…...

阳光倒灌高准直汽车抬头显示器HUD太阳光模拟器

阳光倒灌高准直汽车抬头显示器HUD太阳光模拟器是一种高级别的模拟设备&#xff0c;用于模拟太阳光的光谱、强度及照射角度&#xff0c;应用于太阳能电池板、光伏系统等领域的研究和测试。其参数包括光谱范围、光强度、光源、照射角度、均匀性和稳定性&#xff0c;可根据需求调整…...

jdk11中自定义java类在jvm是如何被查找、加载

yym带你了解jvm源码&#xff0c;openjdk11源码&#xff0c;java类jvm加载原理 jdk11中java类在jvm是如何被1查找、2加载 以下说明的是MiDept类是如何被java classloader 和 jvm加载步骤 上源代码 public static void main(String[] args) {Thread.currentThread().setName…...

单片机---独立按键

[3-1] 独立按键控制LED亮灭_哔哩哔哩_bilibili 按下的时候连接&#xff0c;松开的时候断开。 一头接GND&#xff08;电源负极&#xff09;&#xff0c;另一头接I/O口。 单片机上电时&#xff0c;所有I/O口为高电平。 按键没有按下&#xff0c;I/O口为高电平。 按键按下&…...

java分布式面试快问快答

目录 Java分布式面试宝典50题DubboRedisZookeeper分布式系统设计性能优化与监控安全实践经验 解答DubboRedisZookeeper分布式系统性能优化与监控安全 Java分布式面试宝典50题 Java分布式开发涉及到Dubbo、Redis、Zookeeper等技术&#xff0c;这些技术在实际工作中扮演着重要角…...

AI:148-开发一种智能语音助手,能够理解和执行复杂任务

AI&#xff1a;148-开发一种智能语音助手&#xff0c;能够理解和执行复杂任务 1.背景介绍 随着人工智能技术的飞速发展&#xff0c;智能语音助手已经逐渐成为人们日常生活中不可或缺的一部分。从简单的查询天气、播放音乐&#xff0c;到复杂的日程安排、智能家居控制&#xf…...

Kindling the Darkness:A Practical Low-light Image Enhancer

Abstract 在弱光条件下拍摄的图像通常会出现&#xff08;部分&#xff09;可见度较差的情况。,除了令人不满意的照明之外&#xff0c;多种类型的退化也隐藏在黑暗中&#xff0c;例如由于相机质量有限而导致的噪点和颜色失真。,换句话说&#xff0c;仅仅调高黑暗区域的亮度将不…...

图像处理与视觉感知---期末复习重点(4)

文章目录 一、图像复原与图像增强1.1 概述1.2 异同点 二、图像复原/退化模型2.1 模型图简介2.2 线性复原法 三、彩色基础四、彩色模型五、彩色图像处理 一、图像复原与图像增强 1.1 概述 1. 图像增强技术一般要利用人的视觉系统特性&#xff0c;目的是取得较好的视觉效果&…...

ABAP AMDP 示例

AMDP 是HANA开发中的一种优化模式 按SAP的官方建议&#xff0c;在可以使用Open SQL实现需要的功能或优化目标的时候&#xff0c;不建议使用AMDP。而在需要使用Open SQL不支持的特性&#xff0c;或者是大量处理流和分析导致了数据库和应用服务器之间有重复的大量数据传输的情况…...

发票查验接口C++语言如何集成、发票OCR

说起发票查验工作&#xff0c;繁琐的发票信息录入与反复查验令财务人员头疼不已。数字化时代&#xff0c;企业财务管理的自动化需求越来越高&#xff0c;翔云发票查验API搭配发票识别接口为企业提供一种高效的财务管理解决方案。仅需上传发票图片即可快速提取发票四要素信息&am…...

【图论 | 数据结构】用链式前向星存图(保姆级教程,详细图解+完整代码)

一、概述 链式前向星是一种用于存储图的数据结构,特别适合于存储稀疏图,它可以有效地存储图的边和节点信息,以及边的权重。 它的主要思想是将每个节点的所有出边存储在一起,通过数组的方式连接(类似静态数组实现链表)。这种方法的优点是存储空间小,查询速度快,尤其适…...

【蓝桥杯3.23小白赛】(详解)

第一题签到题不多说 【二进制王国】 #include <iostream> #include <vector> #include <algorithm> using namespace std;//int Cmp(string s1, string s2)测试了一下时间差确实很明显&#xff0c;还是用下面的内个 int Cmp(const string &s1,const st…...

设计模式之抽象工厂模式精讲

概念&#xff1a;为创建一组相关或相互依赖的对象提供一个接口&#xff0c;而且无须指定他们的具体类。 抽象工厂模式是工厂方法模式的升级版本。在存在多个业务品种或分类时&#xff0c;抽象工厂模式是一种更好的解决方式。 抽象工厂模式的UML类图如下&#xff1a; 可以看…...

初识云原生、虚拟化、DevOps

文章目录 K8S虚拟化DevOpsdevops平台搭建工具大数据架构 K8S master 主节点&#xff0c;控制平台&#xff0c;Master节点负责核心的调度、管理和运维&#xff0c;不需要很高性能&#xff0c;不跑任务&#xff0c;通常一个就行了&#xff0c;也可以开多个主节点来提高集群可用度…...

怎麼實現Nginx反向代理?

Nginx是一款開源軟體&#xff0c;可以作為Web伺服器、負載均衡器和反向代理使用&#xff0c;是高性能的HTTP和反向代理伺服器。其中反向代理是Nginx的一項重要特性。接下來&#xff0c;我們詳細講一下Nginx反向代理的實現和應用。 反向代理是什麼&#xff1f; 代理一詞通常指的…...

IOS面试题编程机制 71-75

71. 简述有哪几种手势通知方法?-(void)touchesBegan:(NSSet*)touchedwithEvent:(UIEvent*)event; -(void)touchesMoved:(NSSet*)touched withEvent:(UIEvent*)event; -(void)touchesEnded:(NSSet*)touchedwithEvent:(UIEvent*)event; -(void)touchesCanceled:(NSSet*)touchedw…...

JMeter元件作用域和执行顺序

JMeter元件作用域和执行顺序 元件的基本介绍基本元件总结 作用域的基本介绍作用域的原则元件执行顺序Jmeter第一个案例&#xff1a; Jmeter三个重要组件&#xff08;重点&#xff09;线程组特点线程组分类线程组的属性案例分析 HTTP请求案例一&#xff08;使用HTTP请求路径来传…...

别再只用柱状图了!用Python的Matplotlib画个酷炫的雷达图,5分钟搞定你的个人技能展示

用Python打造专业级技能雷达图&#xff1a;5步提升你的职场竞争力 简历上那些千篇一律的柱状图和百分比条已经让招聘官审美疲劳了&#xff1f;试试用Matplotlib绘制一个令人眼前一亮的雷达图来展示你的核心技能组合。这种可视化方式不仅能清晰呈现你在各个领域的熟练程度&#…...

5分钟搞定:Mac用户制作Windows启动盘的终极指南

5分钟搞定&#xff1a;Mac用户制作Windows启动盘的终极指南 【免费下载链接】windiskwriter &#x1f5a5; A macOS app that creates bootable USB drives for Windows. &#x1f6e0; Patches Windows 11 to bypass TPM and Secure Boot requirements. 项目地址: https://g…...

SPM12实战:从nii文件元数据解析到精准slice timing配置

1. 理解nii文件与slice timing的基础概念 当你第一次拿到fMRI的nii格式数据时&#xff0c;可能会被这个黑箱般的文件格式搞得一头雾水。nii文件就像是把整个大脑扫描过程打包成一个数字包裹&#xff0c;里面不仅包含三维的脑部图像数据&#xff0c;还隐藏着关键的扫描参数。我在…...

如何选择高转化率的关键词_如何优化SEO关键词

<h2>如何选择高转化率的关键词</h2> <p>在现代数字营销中&#xff0c;选择高转化率的关键词是提升网站流量和销售额的关键。一个成功的SEO策略&#xff0c;需要在关键词选择上下足功夫&#xff0c;因为这直接影响到网站的整体效果。本文将从问题分析、原因说…...

BilibiliDown终极指南:如何快速掌握B站视频批量下载技巧

BilibiliDown终极指南&#xff1a;如何快速掌握B站视频批量下载技巧 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors…...

手把手教你用Flotherm做热管仿真

&#x1f393;作者简介&#xff1a;科技自媒体优质创作者 &#x1f310;个人主页&#xff1a;莱歌数字-CSDN博客 &#x1f48c;公众号&#xff1a;莱歌数字&#xff08;B站同名&#xff09; &#x1f4f1;个人微信&#xff1a;yanshanYH 211、985硕士&#xff0c;从业16年 从…...

teler IDS v3前瞻:eBPF技术与teler-waf集成带来的革命性变革

teler IDS v3前瞻&#xff1a;eBPF技术与teler-waf集成带来的革命性变革 【免费下载链接】teler Real-time HTTP Intrusion Detection 项目地址: https://gitcode.com/gh_mirrors/te/teler teler IDS作为一款实时HTTP入侵检测系统&#xff0c;在网络安全领域已经建立了坚…...

Vision Master OpenCV 2.0 深度评测:新增YOLOv5、语义分割等ONNX模型,实战性能提升有多大?

Vision Master OpenCV 2.0 深度评测&#xff1a;ONNX模型实战性能全解析 当计算机视觉开发工具开始拥抱ONNX生态&#xff0c;技术选型的边界正在被重新定义。Vision Master OpenCV 2.0的发布恰逢其时&#xff0c;它不仅将YOLOv5、语义分割等前沿模型集成到可视化流程中&#xf…...

收藏!30岁转行AI大模型,来得及吗?小白程序员必看的真实转型干货

“30岁&#xff0c;人生好像走到了岔路口&#xff0c;转行还来得及吗&#xff1f;”这是很多职场人遭遇瓶颈时&#xff0c;都会反复纠结的问题。尤其是面对AI大模型这样的新兴领域&#xff0c;不少人既心动又胆怯——怕年龄太大、怕没有基础、怕跟不上节奏。但今天我想明确告诉…...

SVN 启动模式详解

SVN 启动模式详解 引言 Subversion(简称SVN)是一个开源的版本控制系统,广泛用于软件项目协作开发中。SVN的启动模式是其基本操作的核心,了解并掌握不同的启动模式对于高效使用SVN至关重要。本文将详细介绍SVN的启动模式,包括基本概念、常用模式及其应用场景。 一、SVN启…...