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

双指针——有效三角形的个数

news 来源：原创 2025/7/2 16:14:09

一.题目描述

611. 有效三角形的个数 - 力扣（LeetCode）

二.题目解析 

题目其实很简单就是让我们在数组中找到可能构成三角形的所有可能。构成三角形的前提是：任意两边之和大于第三边。所以我们要满足让下面三条同时成立才可以构成三角形：1、a+b>c，2、c+b>a，3、a+c>b。

但是我们可以对这个判断逻辑进行优化，我们可以先对三个数进行排序，a<=b<=c，这样我们只需要判断最小的两个数a+b>c即可。这样其实已经暗含了上面的三种情况了。

看着三次判断和一次判断好像不会对时间复杂度有太多的优化，但其实这个优化效果还是很大的。

三.算法原理

1、暴力解法

我们只需要枚举出所有可能的结果，然后依次判断是否可以构成三角形即可。

我们分析一下时间复杂度：三层循环，时间复杂度为O(N^3)，再加上判断是否为三角形所以整体的时间复杂度为O(3*N^3)。 

//伪代码for(i=0; i<n; ++i)for(j=i+1; j<n; ++j)for(k=j+1; k<n; ++k)check(nums[i],nums[j],nums[k]);

 2.利用单调性+双指针

我们首先根据我们优化的逻辑先对数组进行排序，然后我们先选出一个最大的数c，然后用两个指针left、right来遍历剩下的数。我们在遍历的过程中会遇到两种情况：1.a+b>c; 2.a+b<=c.情况不同，我们的处理办法也不同。

当a+b>c时，left~right之间的任意一个数都可以与right以及c构成三角形，因为剩下的数都大于a。因此移动left是没有意义的，因为不管怎么移动都满足。我们只需要统计right和left之间的个数即可：right-left，然后right--。

当a+b<=c时，此时right移动没有意义，因为不管right怎么移动，剩下的值都比现在的小，所以更不可能构成三角形了，此时该区间内不会构成三角形，我们要让left++，在下一个区间内继续查找。

这就是我们这个算法的思路。

时间复杂度为：O(N*logN+N^2)。这个效率比三次方高很多。

空间复杂度为：O(1)。

四.代码实现

最大的那个数没有必要全部都遍历一遍，因为当i<2时，都没有三个数了，没必要判断。

int triangleNumber(vector<int>& nums)
{sort(nums.begin(), nums.end());int ret = 0;int i = 0;for (i = nums.size() - 1; i >= 2; --i){int left = 0;int right = i - 1;while (left < right){if (nums[left] + nums[right] > nums[i]){//可以构成三角形ret += (right - left);right--;}else{//构不成三角形left++;}}}return ret;
}

相关文章：

双指针——有效三角形的个数

一.题目描述 611. 有效三角形的个数 - 力扣&#xff08;LeetCode&#xff09; 二.题目解析 题目其实很简单就是让我们在数组中找到可能构成三角形的所有可能。构成三角形的前提是&#xff1a;任意两边之和大于第三边。所以我们要满足让下面三条同时成立才可以构成三角形&am…...

编程日记 2025/7/2 16:14:09

【ES6复习笔记】函数参数的默认值（6）

在ES6中&#xff0c;函数参数默认值是一个非常有用的特性&#xff0c;它允许你在定义函数时为参数指定一个默认值。如果在调用函数时没有提供相应的参数值&#xff0c;那么函数将使用默认值。 1. 形参初始值 具有默认值的参数&#xff0c;一般位置要靠后。这是一个潜规则&…...

编程日记 2025/7/2 1:39:18

tryhackme-Cyber Security 101-Linux Shells（linux命令框）

目的&#xff1a;了解脚本和不同类型的 Linux shell。 任务1&#xff1a;Introduction to Linux Shells&#xff08;Linux Shell 简介&#xff09; 作为操作系统的常规用户&#xff0c;我们都广泛使用图形用户界面 &#xff08;GUI&#xff09; 来执行大多数操作。只需点击几…...

编程日记 2025/6/28 21:34:21

【Go】-限流器的四种实现方法

目录 关于限流和限流器 固定窗口限流器 滑动窗口限流器 漏桶限流器 令牌桶限流器 总结 关于限流和限流器 限流&#xff08;Rate Limiting&#xff09;是一种控制资源使用率的机制&#xff0c;通常用于防止系统过载和滥用。 限流器&#xff08;Rate Limiter&#xff09;是…...

编程日记 2025/6/29 8:56:42

精准识别花生豆：基于EfficientNetB0的深度学习检测与分类项目

精准检测花生豆&#xff1a;基于EfficientNet的深度学习分类项目 在现代农业生产中&#xff0c;作物的质量检测和分类是确保产品质量的重要环节。针对花生豆的检测与分类需求&#xff0c;我们开发了一套基于深度学习的解决方案&#xff0c;利用EfficientNetB0模型实现高效、准…...

编程日记 2025/6/28 21:41:39

【信息系统项目管理师】第11章：项目成本管理过程详解

更多内容请见： 备考信息系统项目管理师-专栏介绍和目录 文章目录 一、规划成本管理1、输入2、工具与技术3、输出二、估算成本1、输入2、工具与技术3、输出三、制定预算1、输入2、工具与技术3、输出四、控制成本1、输入2、工具与技术3、输出一、规划成本管理 定义：规划成本管…...

编程日记 2025/7/3 8:01:03

微信流量主挑战：用户破16！新增文档转换（新纪元3）

朋友们&#xff0c;报告好消息&#xff01;我的小程序用户数量已经涨到16个了&#xff01;没错&#xff0c;真没拉朋友圈亲戚好友来撑场子&#xff0c;全靠实力&#xff08;和一点点运气&#xff09;吸引了16位陌生小伙伴光临&#xff01;这波进步&#xff0c;连我自己都感动了…...

编程日记 2025/7/2 22:53:28

DFS【东北大学oj数据结构11-2】C++

题面 深度优先搜索&#xff08;DFS&#xff09;是一种基于尽可能多地访问相邻顶点策略的图搜索算法。如果顶点 v 有未搜索的顶点则递归搜索直至 v 的最后一条边。在搜索了 v 的所有边之后&#xff0c;搜索继续返回到找到 v 时经过的边。 搜索从原来的起点开始&#xff0c;直到…...

编程日记 2025/6/28 17:55:01

运维项目部署的环境准备

这里用的安装工具是yum,yum作为一个安装工具,用起来比较方便 用yum安装以下软件,组成项目的可运行环境 yum 先更新 yum update -y 安装一个外置仓库 yum install epel-release 安装redis yum install redis 安装nginx yum install nginx 安装vim yum install vim…...

编程日记 2025/6/28 17:00:38

URDF文件中inertial数据的描述坐标系说明

这件事的来源是这样的&#xff1a;结构手动把连杆坐标系下描述的惯性张量数据写入了urdf中&#xff0c;给我到以后发现有问题&#xff0c;给我搞懵了&#xff0c;以为我错了这么多年&#xff0c;于是有了本次的深度调研&#xff0c;先上结论&#xff0c;感兴趣的可以参考后文。…...

编程日记 2025/6/28 17:00:53

OpenCV-Python实战（5）——图形绘制基础

一、直线 cv2.line(img*,pt1*,pt2*,color*,thickness*,lineTypeLINE_8) img&#xff1a;绘图的背景&#xff08;画布&#xff09;。 pt1、pt2&#xff1a;始/终点坐标&#xff0c;格式为元组&#xff08;&#xff09;。 color&#xff1a;直线颜色&#xff0c;BGR格式。 t…...

编程日记 2025/7/2 0:07:56

科技云报到：人工智能时代“三大件”：生成式AI、数据、云服务

科技云报到原创。 就像自行车、手表和缝纫机是工业时代的“三大件”。生成式AI、数据、云服务正在成为智能时代的“新三大件”。加之全球人工智能新基建加速建设&#xff0c;成为了人类社会数字化迁徙的助推剂&#xff0c;让新三大件之间的耦合越来越紧密。从物理世界到数字世…...

编程日记 2025/6/30 19:35:52

HarmonyOS NEXT 实战之元服务：静态案例效果（二）

背景&#xff1a; 前几篇学习了元服务&#xff0c;后面几期就让我们开发简单的元服务吧&#xff0c;里面丰富的内容大家自己加&#xff0c;本期案例 仅供参考 先上本期效果图 &#xff0c;里面图片自行替换 效果图代码案例如下&#xff1a; Index里面实现 import { authent…...

编程日记 2025/7/2 10:57:26

Qt学习记录

Qt学习记录 Qt6读取GBK文件 在Qt5中&#xff0c;有QTextCodec模块&#xff0c;支持各种编码设置。 // Qt5 QCoreApplication a(argc, argv); auto desk QStandardPaths::writableLocation(QStandardPaths::DesktopLocation); QFile file(QDir(desk).filePath("test.tx…...

编程日记 2025/7/1 22:03:40

用于汽车碰撞仿真的 Ansys LS-DYNA

使用 Ansys LS-DYNA 进行汽车碰撞仿真汽车碰撞仿真 简介 汽车碰撞仿真是汽车设计和安全工程的一个关键方面。这些仿真使工程师能够预测车辆在碰撞过程中的行为&#xff0c;从而有助于改进安全功能、增强车辆结构并符合监管标准。Ansys LS-DYNA 是一款广泛用于此类仿真的强大工具…...

编程日记 2025/7/2 4:28:23

Android--java实现手机亮度控制

文章目录 1、开发需求2、运行环境3、主要文件4、布局文件信息5、手机界面控制代码6、debug 1、开发需求 需求&#xff1a;开发一个Android apk实现手机亮度控制 2、运行环境 Android studio最新版本 3、主要文件 app\src\main\AndroidManifest.xml app\src\main\res\layou…...

编程日记 2025/7/3 5:48:20

300多种复古手工裁剪拼贴艺术时尚字母、数字、符号海报封面Vlog视频MOV+PNG素材

300复古时尚大小写字母、数字、符号拼贴海报封面平面设计Vlog视频标题动画 Overlay - Cut-Out Letters Animations Pack - Animated Letters, Numbers, and Symbols 使用 Cut-Out Letters Animations Pack 提升您的内容&#xff01;包含 300多个高品质动画资源&#xff0c;包括…...

编程日记 2025/7/2 11:11:55

免押租赁系统的优势与应用解析

内容概要 免押租赁系统&#xff0c;听上去是不是很未来&#xff1f;其实&#xff0c;它的基本概念就是在租赁过程中&#xff0c;消费者无需交付押金&#xff0c;直接使用所租物品。这样一来&#xff0c;不仅降低了租赁的门槛&#xff0c;也让许多想尝试的用户能够更轻松地参与…...

编程日记 2025/7/2 0:46:19

feign 针对某一个特定接口设置超时时间

一、对feign所有接口设置超时配置 如果是当前feign所有接口的超时配置&#xff0c;需要在 FeignClient 的 configuration 属性中设置。 详情见&#xff1a; https://blog.csdn.net/sinat_32502451/article/details/136884349 二、针对某一个特定接口设置超时时间 调用 feig…...

编程日记 2025/6/28 17:00:43

Chrome被360导航篡改了怎么改回来？

一、Chrome被360导航篡改了怎么改回来&#xff1f; 查看是否被360主页锁定&#xff0c;地址栏输入chrome://version&#xff0c;看命令行end后面&#xff08;蓝色部分&#xff09;&#xff0c;是否有https://hao.360.com/?srclm&lsn31c42a959f 修改步骤 第一步&#xff1a…...

编程日记 2025/7/2 10:07:32

GitLab 将停止为中国区用户提供服务，60天迁移期如何应对？ | LeetTalk Daily

“LeetTalk Daily”&#xff0c;每日科技前沿&#xff0c;由LeetTools AI精心筛选&#xff0c;为您带来最新鲜、最具洞察力的科技新闻。 GitLab作为一个广受欢迎的开源代码托管平台&#xff0c;近期宣布将停止服务中国大陆、澳门和香港地区的用户提供服务。根据官方通知&#x…...

编程日记 2025/7/1 11:13:37

Linux系统和makefile详解

### Linux系统详解 Linux是一个开源且功能强大的操作系统内核&#xff0c;自1991年由林纳斯托瓦兹首次发布以来&#xff0c;它已经成为全球最流行的操作系统之一。Linux的核心特性包括开源、多用户多任务、高稳定性与安全性&#xff0c;以及良好的跨平台能力。 1. **开源**&a…...

编程日记 2025/7/2 3:30:39

基于导频方法的MIMO信道估计详解

多输入多输出&#xff08;MIMO&#xff09;技术作为现代无线通信系统的核心&#xff0c;通过利用多天线阵列在发射端和接收端同时传输和接收多个数据流&#xff0c;显著提高了系统的频谱效率和数据传输速率。然而&#xff0c;MIMO系统的性能在很大程度上依赖于对信道状态的准确…...

编程日记 2025/6/30 22:03:58

#!/bin/bash^M 坏的解释器：没有哪个文件或者目录

#!/bin/bash^M 坏的解释器&#xff1a;没有哪个文件或者目录 问题背景问题分析问题解决dos2unixsedvim编辑器&#xff08;推荐&#xff09;在Windows上转换文件格式 最后 问题背景 工作中&#xff0c;在Windows上编写的shell脚本上传到Linux服务器&#xff0c;在执行的时候提示…...

编程日记 2025/7/3 8:01:04

aj-report本地前后端分离部署运行

github项目地址 aj-report-mine 在源代码v1.4版本基础上&#xff0c;本地进行前后端分离部署开发 这里我是进行了整合&#xff0c;把自己在拉取源代码到成功运行过程中的一些东西直接整合&#xff0c;根据下面的步骤即可成功运行 资源获取 夸克网盘(16-github-aj-report-re…...

编程日记 2025/7/2 3:17:30

1435A 信号发生器

1435A 信号发生器 1435系列信号发生器基于创新的技术实现了性能、经济性和体积重量的平衡设计。具有优良的频谱纯度&#xff0c;单边带相位噪声1GHz载波10kHz频偏达到-136dBc/Hz&#xff0c;10GHz载波10kHz频偏达到-116dBc/Hz&#xff1b;具有高功率输出和大动态范围&#xff…...

编程日记 2025/7/2 22:56:48

计算机组成原理的学习笔记(9)-- CPU·其一 CPU的基本概念/流水线技术/数据通路

学习笔记 前言 ​ 本文主要是对于b站尚硅谷的计算机组成原理的学习笔记&#xff0c;仅用于学习交流。 CPU&#xff08;中央处理器&#xff09; 1. 组成 定义&#xff1a;计算机的核心部件&#xff0c;负责执行指令和处理数据。 组成部分&#xff1a; 核心&#xff1a;多个处…...

编程日记 2025/7/3 5:44:45

【Python】 -- python3 读取 aws athena 表数据

目录 1、环境准备 2、安装环境 3、举例查询某张表数据和执行 add partition 操作 3.1、编辑文件 athena_jdbc.py 3.2、查找 JVM 的动态链接库路径 3.3、保存文件&#xff0c;执行以下命令 1、环境准备 oracle jdk 11centos 8依赖&#xff1a;pandas、pyathenajdbc 和 sq…...

编程日记 2025/6/30 19:17:04

子网掩码计算route命令

子网掩码 - 站长工具 1.子网掩码 子网掩码就是用来遮掩IP地址并划分网段的工具&#xff0c;根据遮掩的位数不同来划分不同的网段。 2.网关 网关(Gateway)又称网间连接器、协议转换器。默认网关在网络层上以实现网络互连&#xff0c;是最复杂的网络互连设备&#xff0c;仅用…...

编程日记 2025/6/28 19:49:59

店铺营业状态设置

admineShopController RestController("admineShopController") RequestMapping("/admin/shop") Api(tags "店铺相关接口") Slf4j public class ShopController {//设置一个常量 因为经常使用public static final String KEY "SHOP-ST…...

编程日记 2025/7/1 22:27:29

JavaWeb 开发基础入门

在当今互联网时代&#xff0c;JavaWeb 开发是构建各类网络应用的核心技术之一。无论是大型企业级应用&#xff0c;还是小型的个人网站&#xff0c;JavaWeb 都展现出强大的生命力。今天&#xff0c;就让我们一起踏入 JavaWeb 开发的基础入门之旅。 一、认识 JavaWeb JavaWeb 是…...

编程日记 2025/6/28 20:23:26

Unity Dots理论学习-2.ECS有关的模块（1）

Unity的实体组件系统&#xff08;ECS&#xff09;是支撑DOTS模块和技术的面向数据架构。ECS为Unity中的内存数据和runtime进程调度提供了高度的控制和确定性。 ECS for Unity 2022 LTS 配备了两个兼容的物理引擎&#xff0c;一个高级的Netcode package&#xff0c;以及一个用来…...

编程日记 2025/7/2 0:46:49

CentOS下安装RabbitMQ

提示：“奔跑吧邓邓子” 的高效运维专栏聚焦于各类运维场景中的实际操作与问题解决。内容涵盖服务器硬件（如 IBM System 3650 M5）、云服务平台（如腾讯云、华为云）、服务器软件（如 Nginx、Apache、GitLab、Redis、Elasticsearch、Kubernetes、Docker 等）、开发工具（如 Gi…...

编程日记 2025/7/1 7:18:46

【JAVA高级篇教学】第四篇：MySQL 5.7 与 MySQL 8 的区别

MySQL 是最流行的开源数据库管理系统之一&#xff0c;而 MySQL 8 的发布相较于 MySQL 5.7 带来了大量的改进与功能增强。 目录 一、性能改进 二、功能增强 三、安全性 四、开发体验 五、默认排序规则 六、支持的排序规则数量 七、区分敏感性&#xff08;Sensitivity&…...

编程日记 2025/6/28 2:13:31

【Git】-- 版本说明

Alpha&#xff1a;是内部测试版,一般不向外部发布,会有很多 Bug .一般只有测试人员使用。Beta&#xff1a;也是测试版&#xff0c;这个阶段的版本会一直加入新的功能。在 Alpha 版之后推出。RC&#xff1a;(Release　Candidate) 顾名思义么 ! 用在软件上就是候选版本。系统平台…...

编程日记 2025/7/3 6:27:00

Flink优化----FlinkSQL 调优

目录 FlinkSQL 调优 1 设置空闲状态保留时间 2 开启 MiniBatch 3 开启 LocalGlobal 3.1 原理概述 3.2 提交案例&#xff1a;统计每天每个 mid 出现次数 3.3 提交案例&#xff1a;开启 miniBatch 和 LocalGlobal 4 开启 Split Distinct 4.1 原理概述 4.2 提交案例&…...

编程日记 2025/7/2 9:29:32

云上「算力浪费」，正在掣肘企业应用落地。

投入算力&#xff0c;真的能换来利润吗&#xff1f;这是每个想“入局”大模型的企业都会思考的问题。 人工智能行业一直困于成本&#xff0c;无论从模型训练到推理&#xff0c;都充满了“烧钱”的气息。无法避免的高昂算力&#xff0c;成为企业入局大模型的“铁门槛”。 据多…...

编程日记 2025/7/2 4:15:24

科技创新 数智未来｜清科·沙丘投研院走进竹云

12月20日&#xff0c;清科沙丘投研院带领企投家团队走进竹云交流分享&#xff0c;聚焦技术创新、企业数字化管理、行业前沿应用案例等热点议题&#xff0c;深入探讨数字技术如何点燃企业高质量发展的澎湃动力&#xff0c;共话企业数字化、智能化发展之道。 达晨财智股权管理部…...

编程日记 2025/7/2 10:06:42

spring专题笔记（六）：bean的自动装配（自动化注入）-根据名字进行自动装配、根据类型进行自动装配。代码演示，通俗易懂。

目录 一、根据名字进行自动装配--byName 二、根据类型进行自动装配 byType 本文章主要是介绍spring的自动装配机制&#xff0c; 用代码演示spring如何根据名字进行自动装配、如何根据类型进行自动装配。代码演示&#xff0c;通俗易懂。 一、根据名字进行自动装配--byName Us…...

编程日记 2025/6/30 7:09:00

EDGE浏览器每次关闭时再次打开保存的密码就消失如何解决

文章目录 EDGE浏览器每次重启的时候保存的密码都消失如何解决&#xff1f; 打开EDGE浏览器点击三个点 点击设置 点击隐私、搜索和服务 找到选择每次关闭浏览器时要清除的内容 将开启的关闭即可...

编程日记 2025/7/2 3:32:55

Python - 获取当前函数中的所有参数信息（名称和值）

代码 import inspect import randomclass P:def start(self, p1, p2, p3None, p4None):arg_info inspect.getargvalues(inspect.currentframe())kwargs arg_info.locals # 获取到所有参数print(kwargs)del kwargs["self"]try:self._start(**kwargs)except Except…...

编程日记 2025/7/2 3:29:12

pyqt5冻结+分页表

逻辑代码 # -*- coding: utf-8 -*- import sys,time,copy from PyQt5.QtWidgets import QWidget,QApplication, QDesktopWidget,QTableWidgetItem from QhTableWidgetQGN import Ui_QhTableWidgetQGN from PyQt5.QtCore import Qt from PyQt5 import QtCore, QtGui, QtWidgets…...

编程日记 2025/6/30 1:45:10

uniapp中实现APP调用本地通知栏通知、震动、本地提示音或者mp3提醒

要在uniapp中实现APP调用本地通知栏通知、震动和本地提示音或者mp3提醒&#xff0c;你可以使用uni-app提供的原生API和插件来实现。 通知栏通知&#xff1a; 你可以使用uni-app的原生API uni.showToast() 或者 uni.showModal() 来实现通知栏通知的功能。可以在需要发送通知的地…...

编程日记 2025/7/2 0:45:37

JS 数组创建、访问、常用方法

文章目录 创建访问常用属性和相关方法1. length 长度属性2. push() 新增元素 - 末尾添加3. unshift() 新增元素 - 开头添加4. pop() 移除元素 - 末尾删除5. shift() 移除元素 - 开头删除6. concat() 复制数组后新增7. slice() 复制数组8. splice() 增删改9. toString() 转字符串…...

编程日记 2025/7/2 20:59:57

【C++】ceil 和 floor 函数的实现与分析

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;ceil 和 floor 函数的基础介绍1. ceil 函数定义与功能示例代码输出结果功能分析使用场景 2. floor 函数定义与功能示例代码输出结果功能分析使用场景 &#x1f4af;自行实现…...

编程日记 2025/6/29 23:19:17

每天40分玩转Django：Django类视图

Django类视图 一、今日学习内容概述 学习模块重要程度主要内容类视图基础⭐⭐⭐⭐⭐View类、URLconf配置通用视图⭐⭐⭐⭐⭐ListView、DetailView等Mixin机制⭐⭐⭐⭐多重继承、功能组合自定义类视图⭐⭐⭐⭐视图定制、方法重写 二、类视图基础 2.1 基本类视图 # views.py…...

编程日记 2025/6/28 5:51:21

运动控制卡网络通讯的心跳检测之C#上位机编程

本文导读 今天&#xff0c;正运动小助手给大家分享一下如何使用C#上位机编程实现运动控制卡网络通讯的心跳检测功能。 01 ECI2618B硬件介绍 ECI2618B经济型多轴运动控制卡是一款脉冲型、模块化的网络型运动控制卡。控制卡本身最多支持6轴&#xff0c;可扩展至12轴的运动控制…...

编程日记 2025/7/3 5:48:20

秒验简介与下载说明

秒验简介与下载说明 产品概述 秒验是一款帮助开发者实现一键验证功能的产品&#xff0c;从根源上降低企业验证成本&#xff0c; 有效提高拉新转化率&#xff0c;降低因验证带来的流失率&#xff0c;3秒完成手机号验证 SDK信息 下载SDK 下载地址 SDK提供Maven和pod引入两种方…...

编程日记 2025/7/2 7:26:40

Redis中的数据类型

文章目录 前言一、字符串&#xff08;String&#xff09;应用场景常用命令 二、哈希&#xff08;Hash&#xff09;应用场景常用命令 三、列表&#xff08;List&#xff09;应用场景常用命令 四、集合&#xff08;Set&#xff09;应用场景常用命令 五、有序集合&#xff08;Sort…...

编程日记 2025/7/2 12:35:03

esp8266_TFTST7735语音识别UI界面虚拟小助手

文章目录 一 实现思路1 项目简介1.1 项目效果1.2 实现方式 2 项目构成2.1 软硬件环境2.2 完整流程总结&#xff08;重点整合&#xff09;(1) 功能逻辑图(2) 接线(3) 使用esp8266控制TFT屏(4)TFT_espI库配置方法(5) TFT_esp库常用代码详解(6)TFT屏显示图片(7) TFT屏显示汉字(8) …...

编程日记 2025/7/2 8:38:13