LeetCode 分类刷题: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 可以知道,对于三元组 (2,3,4) 和 (4,3,2),我们只统计了其中的 (2,3,4),并没有把 (4,3,2) 也统计到答案中,所以题目意思是把这两个三元组当成是同一个三元组,我们不能重复统计。

既然有这样的规则,那么不妨规定三角形的三条边 a,b,c 满足:1 ≤ a ≤ b ≤c
这可以保证我们在统计合法三元组 (a,b,c) 的个数时,不会把 (c,b,a) 这样的三元组也统计进去。

那么问题变成,从 nums 中选三个数,满足 1≤a≤b≤c 且 a+b>c 的方案数。

采用方法:枚举最长边 + 相向双指针

为了能够使用相向双指针,先对数组从小到大排序。 外层循环枚举最长边 c=nums[k],内层循环用相向双指针枚举 a=nums[i] 和 b=nums[j],具体如下:

  1. 初始化左右指针 i=0, j=k−1。
  2. 如果 nums[i]+nums[j]>c,由于数组是有序的,nums[j] 与下标 i' 在 [i,j−1] 中的任何 nums[i'] 相加,都是 >c 的,因此直接找到了 j−i 个合法方案,加到答案中,然后将 j 减一。
  3. 如果 nums[i]+nums[j]≤c,由于数组是有序的,nums[i] 与下标 j' 在 [i+1,j] 中的任何 nums[j'] 相加,都是 ≤c 的,因此后面无需考虑 nums[i],将 i 加一。
  4. 重复上述过程直到 i≥j 为止。

与 LeetCode Hot 100:15. 三数之和-CSDN博客 类似,

在设立相向双指针之前,有两个优化:

作者:灵茶山艾府
链接:https://leetcode.cn/problems/valid-triangle-number/solutions/2432875/zhuan-huan-cheng-abcyong-xiang-xiang-shu-1ex3/
来源:力扣(LeetCode)

答案

/*** @param {number[]} nums* @return {number}*/
var triangleNumber = function(nums) {nums.sort((a, b) => a - b);let ans = 0;for(let k = nums.length - 1; k > 1; k--) {    //倒序枚举if(nums[0] + nums[1] > nums[k]) {    //最小两数之和都大于最大数(边)ans += (k+1) * k * (k-1) / 6;    //任选三条边都可以构成一个三角形break;}if(nums[k-2] + nums[k-1] <= nums[k]) continue;    //次大两数之和都小于最大数let i = 0, j = k - 1;while(i < j) {if(nums[i] + nums[j] > nums[k]) {    //从nums[i]到nums[j-1]都可以作为最短边ans += j - i;j--;    //找新的第二短边} else {i++;    //找新的最短边}}}return ans;
};

复杂度分析

时间复杂度:O(n^2),其中 n 为 nums 的长度。

空间复杂度:O(1)。不计入排序的栈开销,仅用到若干额外变量。

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

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

相关文章

MATLAB深度学习之数据集-数据库构建方法详解

前言 在MATLAB中&#xff0c;训练深度学习模型时&#xff0c;数据库的构建与输入是关键十分关键的一环&#xff0c;真对不同的数据类型和训练样本&#xff0c;正确的数据构建是训练代码跑通的基本前提。 本文章主要基于matlab官方文档内容和实际应用问题、技巧进行的总结。 …

Linux《进程间通信(上)》

在以上的动静态库的章节当中我们了解了库的制作和原理&#xff0c;了解到了.o文件以及动静态库的本质上都是FLF格式的文件&#xff0c;还了解了ELF文件各个的组成部分。接下来在本篇开始我们就将学习Linux当中又一重要的章节——进程间通信。在进程间通信的学习当中我们将了解到…

Vue2博客项目笔记(完结)

this.$emit(load): 子组件负责监听,然后告诉父组件,父组件来执行 load 方法 <div ref"scroll" >ref"scroll"&#xff1a;给元素取引用名&#xff0c;在 JS 中可以通过 this.$refs.scroll 拿到这个元素 <slot></slot> :用于把父组件传入的…

WinForm之ListView 组件

在 WinForm 中&#xff0c;ListView是用于展示列表型数据的灵活控件&#xff0c;支持多种视图模式&#xff08;如详情列表、图标、列表等&#xff09;&#xff0c;可展示带有图标、多列属性的项目&#xff08;如文件列表、产品信息&#xff09;&#xff0c;兼具展示和交互功能&…

2025年渗透测试面试题总结-01(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 常见面试题 一、有趣的挖洞经历 二、高频漏洞及修复方案 三、渗透工具链及特点 四、WAF绕过技术 五、系…

C++(线程)

一、线程1、线程构造函数类模板原型&#xff1a;template <class Fn, class... Args>explicit thread (Fn&& fn, Args&&... args);1&#xff09;thread&#xff08;线程的构造函数&#xff09;格式&#xff1a;#include <thread>thread 线程名(回调…

cf.训练

1. Buying Lemonade Buying Lemonade 解题思路&#xff1a; 排序&#xff1a;将插槽的罐数 a 从小到大排序&#xff08;sort(a, an)&#xff09;。 特殊情况处理&#xff1a; 若最小罐数足够大&#xff08;a[0] > k/n 且 k%n0&#xff09;或 k1&#xff0c;直接输出 k&…

JAVA无人共享球杆柜系统球杆柜租赁系统源码支持微信小程序

JAVA无人共享球杆柜系统&#xff1a;物联网小程序打造高尔夫租赁新体验市场机遇与行业痛点1. 高尔夫球杆租赁市场蓝海市场规模快速增长&#xff1a;2023年中国高尔夫球杆行业市场规模达到14.77亿元&#xff0c;预计2024年将突破15.75亿元。全球高尔夫装备市场2024年达到132.6亿…

uniapp Android App集成支付宝的扫码组件mPaaS

第一步&#xff0c;设置包名&#xff0c;下载插件导项目中 在manifest.json中添加package, 设置完指定的包名后&#xff1a;Hbuilderx打包时包名也会变化 变成 下载插件导项目中&#xff0c; 第二步&#xff1a;进入阿里云mPaas后台完成代码配置&#xff0c;下载配置文件http…

Effective C++ 条款22: 将成员变量声明为private

Effective C 条款22&#xff1a;将成员变量声明为private核心思想&#xff1a;始终将成员变量声明为private&#xff0c;通过函数接口控制访问&#xff0c;提供封装弹性、精确访问控制和一致性维护点。 ⚠️ 1. 公开成员的致命缺陷 数据一致性破坏&#xff1a; class AccessPoi…

Java基础-斗地主游戏

目录 案例要求&#xff1a;​ 实现思路&#xff1a; 代码&#xff1a; Main启动类&#xff1a; Card实体类&#xff1a; Room操作类&#xff1a; 总结&#xff1a; 案例要求&#xff1a; 实现思路&#xff1a; 1构造卡牌,细节&#xff1a;实体类另设一个int类型变量表示…

基于Java的AI/机器学习库(Smile、Weka、DeepLearning4J)的实用

基于Java和AI技术处理动漫视频 以下是一些基于Java和AI技术处理动漫视频(如《亚久斗》)的实用案例和实现方法,涵盖视频分析、风格转换、角色识别等方向。每个案例均提供技术思路和关键代码片段。 视频关键帧提取 使用OpenCV提取动漫视频中的关键帧,保存为图片供后续分析…