每日一练【有效三角形的个数】

一、题目描述

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

二、题目解析:

思路一:暴力枚举

暴力枚举无需多言,就是三个嵌套循环,思路最简单,复杂度也是最高O(N3)

思路二:利用单调性,使用双指针算法解决问题

我们要明确如何判断3个数能否构成三角形,第一种是任意两边之和要大于第三条边,但这种需要比较3次,比较繁琐;还有另一种只用比较一次就可以判读的方法:

将需要比较的三个数进行排序,我们只需要判断最小的两个数大于最大的数即可,另外两种不需要比较,因为另外两种肯定要加上最大值,显而易见,省去了比较的过程。

那排好序,如何用双指针的方法解决呢?

也是同样定义左右两个指针,

1、如果大于,说明最小的左指针加上都满足,那么比左指针大的数一定都满足,所以计算个数。然后右指针--,准备进行下一组的比较。

2、如果小于,说明右指针最大值都不满足,那么右边的数一定都不满足,所以需要left++,进行下一组的比较。

三、原码:

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int sum = 0;
        //先进行快排,递增顺序
        sort(nums.begin(),nums.end());
        //利用双指针解决问题
        for(int i = nums.size()-1;i>=2;i--)//固定最大数
        {
            int left = 0;
            int right = i-1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    sum += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return sum;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/222902.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《WebGIS快速开发教程》第5版“惊喜”更新啦

我的书籍《WebGIS快速开发教程》第5版&#xff0c;经过忙碌的编写&#xff0c;终于发布啦&#xff01; 先给大家看看新书的封面&#xff1a; 这次的封面我们经过了全新的设计&#xff0c;不同于以往的任何一个版本。从封面就可以看出第5版肯定有不小的更新。 那么我们话不多说…

ChatGPT,作为一种强大的自然语言处理模型,具备显著优势,能够帮助您在各个领域取得突破

2023年随着OpenAI开发者大会的召开&#xff0c;最重磅更新当属GPTs&#xff0c;多模态API&#xff0c;未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义&#xff0c;不亚于互联网和个人电脑的问世。360创始人周鸿祎认为未来各行各业如果不能搭上这班车…

Linux服务器部署XXL-JOB

参考文档及下载地址&#xff1a;分布式任务调度平台XXL-JOB 1 从git拉取XXL-JOB代码 我们的大部分变动&#xff0c;是发生在xxl-job-admin&#xff0c;最终将这个模块打包成jar包部署在linux服务器上。 2 执行数据库脚本 doc\db\tables_xxl_job.sql 3 修改pom文件&#xff0c…

【Linux】信号的保存和捕捉

文章目录 一、信号的保存——信号的三个表——block表&#xff0c;pending表&#xff0c;handler表sigset_t信号集操作函数——用户层sigprocmask和sigpending——内核层 二、信号的捕捉重谈进程地址空间&#xff08;第三次&#xff09;用户态和内核态sigaction可重入函数volat…

语义分割 LR-ASPP网络学习笔记 (附代码)

论文地址&#xff1a;https://arxiv.org/abs/1905.02244 代码地址&#xff1a;https://github.com/WZMIAOMIAO/deep-learning-for-image-processing/tree/master/pytorch_segmentation/lraspp 1.是什么&#xff1f; LR-ASPP是一个轻量级语义分割网络&#xff0c;它是在Mobil…

如何做好软文推广的选题?媒介盒子分享常见套路

选题是软文推广的重中之重&#xff0c;主题选得好&#xff0c;不仅能够戳到用户&#xff0c;提高转化率&#xff0c;还能让各位运营的写作效率大幅度提升&#xff0c;今天媒介盒子就来和大家分享软文选题的常见套路&#xff0c;助力各位品牌进行选题。 一、 根据产品选题 软文…

安卓开发APP应用程序和苹果iOS开发APP应用程序有什么区别?

随着智能手机和平板电脑在全球的普及&#xff0c;APP移动应用已成为日常生活中不可或缺的组成部分。从社交网络到电子商务平台&#xff0c;从个人理财到游戏娱乐&#xff0c;APP几乎渗透了人们所有的活动领域。在开发APP时&#xff0c;开发者通常要面对两大主流平台&#xff1a…

鸿蒙4.0开发笔记之ArkTS语法基础的UI描述、基础组件的使用与如何查看组件是否有参数(八)

文章目录 一、声明式UI描述1、无/有参数组件2、如何查看组件是否有参数 二、Image组件的使用三、组件的属性设置四、补充1、使用组件的成员函数配置组件的事件方法2、配置子组件3、多组件嵌套 一、声明式UI描述 在HarmonyOS的ArkTS语法中&#xff0c;万物皆组件。ArkTS以声明方…

Spring-Boot---配置文件

文章目录 配置文件的作用配置文件的格式PropertiesProperties基本语法读取Properties配置文件 ymlyml基本语法读取yml配置文件 Properties VS Yml 配置文件的作用 整个项目中所有重要的数据都是在配置文件中配置的&#xff0c;具有非常重要的作用。比如&#xff1a; 数据库的…

【TiDB理论知识09】TiFlash

一 TiFlash架构 二 TiFlash 核心特性 TiFlash 主要有 异步复制、一致性、智能选择、计算加速 等几个核心特性。 1 异步复制 TiFlash 中的副本以特殊角色 (Raft Learner) 进行异步的数据复制&#xff0c;这表示当 TiFlash 节点宕机或者网络高延迟等状况发生时&#xff0c;Ti…

SCAU:18049 迭代法求平方根

18049 迭代法求平方根 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 填空题 语言: G;GCC;VC Description 使用迭代法求a的平方根。求平方根的迭代公式如下&#xff0c;要求计算到相邻两次求出的x的差的绝对值小于1E-5时停止&#xff0c;结果显示4位小…

神经网络模型流程与卷积神经网络实现

神经网络模型流程 神经网络模型的搭建流程&#xff0c;整理下自己的思路&#xff0c;这个过程不会细分出来&#xff0c;而是主流程。 在这里我主要是把整个流程分为两个主流程&#xff0c;即预训练与推理。预训练过程主要是生成超参数文件与搭设神经网络结构&#xff1b;而推理…

Redis集群:Sentinel哨兵模式(图文详解)

在 Redis 主从复制模式中&#xff0c;因为系统不具备自动恢复的功能&#xff0c;所以当主服务器&#xff08;master&#xff09;宕机后&#xff0c;需要手动把一台从服务器&#xff08;slave&#xff09;切换为主服务器。在这个过程中&#xff0c;不仅需要人为干预&#xff0c;…

vue3项目中前端导出word文档和导出excel文档

一、导出word文档 参考文章https://blog.csdn.net/qq_53722480/article/details/130017092 1、使用到的包如下&#xff1a; "docxtemplater": "^3.42.4", "file-saver": "^2.0.5", "jszip-utils": "^0.1.0", &q…

【分享】PDF文件不能编辑的3个原因

PDF文件具有很好的兼容性&#xff0c;可靠性&#xff0c;安全性&#xff0c;是很多人办公常用的电子文档格式。但有时候想要编辑PDF时&#xff0c;却发现不能编辑&#xff0c;是什么原因呢&#xff1f;下面小编来分享一下常见的3个原因。 原因1&#xff1a; PDF文件是扫描件&a…

6G网络将于2030年推出?它与5G相比都有哪些提升?

在这之前&#xff0c;我们曾为大家报道了苹果放弃5G调整解调器的研究工作「有消息称苹果将放弃 5G 调制解调器的研究&#xff0c;你了解调制解调器吗&#xff1f;」&#xff0c;如今又有报道称由于5G调整解调器开发遇到困难&#xff0c;苹果将加大对于6G蜂窝连接的开发。你知道…

第四届传智杯初赛(莲子的机械动力学)

题目描述 题目背景的问题可以转化为如下描述&#xff1a; 给定两个长度分别为 n,m 的整数 a,b&#xff0c;计算它们的和。 但是要注意的是&#xff0c;这里的 a,b 采用了某种特殊的进制表示法。最终的结果也会采用该种表示法。具体而言&#xff0c;从低位往高位数起&#xf…

GEE:构建和调用自己的 js 函数库

作者&#xff1a;CSDN _养乐多_ 本文记录了在Google Earth Engine&#xff08;GEE&#xff09;上构建自己的 js 函数库的步骤。构建自己的函数库以方便代码调用和扩展。 文章目录 一、创建lib文件二、调用lib库三、附加3.1 定义函数3.2 js 库中函数互相调用 一、创建lib文件 …

什么?你还不会 OpenTiny 跨框架组件库适配微前端?

本文由体验技术团队 TinyVue 组件库成员陈家梅同学分享&#xff0c;带你手把手实现 TinyVue 组件库适配微前端~ 一、前言 以下是我对微前端的一些粗浅理解&#xff0c;对微前端有一定了解的话可以略过&#xff0c;直接进入第二部分。 1、微前端是什么&#xff1f; 我们首先…

Vue项目使用Sortable.js实现拖拽功能

想了解更多-可前往 Sortable.js官网 查看组件属性及参数 安装组件&#xff08;我这里使用的是NPM安装&#xff09; npm install sortablejs --save在需要使用拖拽功能的页面中使用&#xff08;完整功能代码&#xff09; <div class"tag_box"><div class&q…