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

力扣算法题——611.有效三角形的个数

目录

💕1.题目

💕2.解析思路

本题思路总览

借助排序与双指针探索规律

从规律到代码实现的转化

双指针的具体实现

代码整体流程

💕3.代码实现

💕4.完结


 

 

二十七步也能走完逆流河吗

💕1.题目


💕2.解析思路

本题思路总览

力扣题目要求从给定的整数数组 nums 中找出可以构成三角形的三元组数量。根据三角形的性质,对于三条边 abc,需要满足任意两边之和大于第三边,即 a + b > ca + c > b 且 b + c > a。当数组有序时,只要满足最小的两边之和大于最大边,就可以构成三角形。我们采用排序加双指针的方法,先对数组进行排序,然后固定最大边,使用双指针在其左侧寻找满足条件的另外两条边,通过统计符合条件的组合数量得到最终结果。


借助排序与双指针探索规律

  1. 排序的作用

对数组 nums 进行排序后,数组元素从小到大排列。这样在后续寻找三角形组合时,我们可以固定最大边,只需要关注较小的两条边之和是否大于最大边这一个条件,简化了判断逻辑。


 
  1. 双指针的运用

使用三个指针 abc,其中 c 指向当前考虑的最大边,b 和 a 作为双指针在 c 左侧的元素中移动。b 初始化为 c - 1a 初始化为数组起始位置。通过移动 a 和 b 指针,在 a < b 的条件下,不断检查 nums[a] + nums[b] 与 nums[c] 的大小关系,从而找出所有满足条件的组合。


从规律到代码实现的转化

基于上述排序和双指针的规律,我们在代码中首先对数组进行排序,然后通过两层循环来实现指针的移动和条件判断。外层循环固定最大边 c,从数组末尾向前移动;内层循环使用双指针 a 和 b 在 c 左侧寻找满足三角形条件的组合,并统计组合数量。


双指针的具体实现

  1. 指针定义

a:作为左指针,初始时指向数组的第一个元素,用于表示三角形的最小边。
b:作为右指针,初始时指向 c - 1,用于表示三角形的中间边。
c:用于固定当前考虑的最大边,初始时指向数组的最后一个元素。


2. 指针移动规则

当 nums[a] + nums[b] > nums[c] 时,说明以 nums[b] 为中间边,nums[a] 到 nums[b - 1] 都可以与 nums[b] 和 nums[c] 构成三角形,所以满足条件的组合数量增加 b - a 个,然后将 b 指针左移一位,继续寻找其他组合。

 

当 nums[a] + nums[b] <= nums[c] 时,说明当前 nums[a] 太小,需要将 a 指针右移一位,尝试增大两边之和。


3. 终止条件

内层循环的终止条件是 a >= b,表示已经遍历完当前 c 固定时所有可能的 a 和 b 组合。外层循环的终止条件是 c < 2,因为当 c 小于 2 时,无法构成三角形。


代码整体流程

  1. 数组排序

使用 sort(nums.begin(), nums.end()) 对数组进行排序,确保数组元素按从小到大排列。


 
  1. 初始化变量

初始化计数器 count 为 0,用于统计满足条件的三角形组合数量。同时初始化指针 abcc 指向数组末尾,b 指向 c - 1a 指向数组起始位置。


  1. 外层循环

从数组末尾开始,将 c 指针逐步向左移动,每次移动后更新 b 指针为 c - 1a 指针为数组起始位置。


  1. 内层循环

在 a < b 的条件下,根据 nums[a] + nums[b] 与 nums[c] 的大小关系移动 a 和 b 指针,并更新 count 的值。


  1. 返回结果

当外层循环结束后,返回计数器 count 的值,即为可以构成三角形的三元组数量。

 

通过以上步骤,我们可以利用排序和双指针准确找出数组中可以构成三角形的三元组数量。


💕3.代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //先排成有序
        sort(nums.begin(),nums.end());
        int a = 0;
        int c = nums.size()-1;
        int b = c-1;
        int count = 0;
        while(c>=2)
        {
            while(a<b){
            if(nums[a]+nums[b]>nums[c])
            {
                count += b-a;
                b--;
               //a = 0;可以没有
               //因为b缩小了,如果想要大于c的话,a必须增大,没必要从头开始再遍历
            }
            else
            {
                a++;
            }
            }
            c--;
            b = c-1;
            a = 0;
        }
        return count;

    }
};


💕4.完结


http://www.kler.cn/a/520792.html

相关文章:

  • ThreadLocal概述、解决SimpleDateFormat出现的异常、内存泄漏、弱引用、remove方法
  • K8s运维管理平台 - xkube体验:功能较多
  • Level DB --- TableBuilder
  • 写一个存储“网站”的网站前的分析
  • 《探秘:人工智能如何为鸿蒙Next元宇宙网络传输与延迟问题破局》
  • debian12.9编译freeswitch1.10.12【默认安装】
  • Java 大视界 -- Java 大数据在元宇宙中的关键技术与应用场景(65)
  • 如何运用python技术搭建一个导航网站?
  • 关于安卓compose在gradle8.0上,版本依赖的问题
  • Pyecharts之图表样式深度定制
  • ubuntu无法上网的解决办法
  • 【漫话机器学习系列】061.线性回归参数计算(Finding Linear Regression Parameters)
  • 智能交互革命:论UI-TARS技术突破与未来图景
  • AI刷题-最小化团建熟悉程度和
  • 【java数据结构】HashMapOJ练习题
  • vim的多文件操作
  • 【Rust自学】15.1. 使用Box<T>智能指针来指向堆内存上的数据
  • docker入门——多用户服务器管理(小白)
  • 实战网络安全:渗透测试与防御指南
  • 汽车行业敏捷转型的推动者:ScrumCN的优势与实践
  • GESP2024年3月认证C++六级( 第三部分编程题(1)游戏)
  • 【ES实战】治理项之索引模板相关治理
  • React 前端框架实战教程
  • skynet 源码阅读 -- 「揭秘 Skynet 网络通讯」
  • C语言I/O请使用互斥锁和信号量分别实现5个线程之间的同步
  • java求职学习day17