LeetCode.611有效三角形的个数

news/2025/2/12 2:02:53/

题目链接611. 有效三角形的个数 - 力扣(LeetCode)

1.常规解法(会超时)

由于构成三角形的条件为两边之和大于第三边,就可以遍历该数组,找到所有满足这个条件的三元组,代码如下:

java">    public int triangleNumber(int[] nums) {int count = 0;int n = nums.length;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] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {count++;}}}}return count;}

2.双指针算法

再常规解法中,我们要循环遍历这个数组三次,而且对每一个三元组都要判断三次,过于麻烦。

java">a + b > c     1
a + c > b     2
b + c > a     3

对于上面三个条件,若已知a, b, c是从小到大排列,那么c就是最大的数,2,3式就必然成立,只需判断1式是否成立即可。

先对数组从小到大排序,再定义指针left,right和p,left指向首元素,p指向末元素,right指向p前一个元素,此时p所指向的元素就是最大的,相当于c,right次之,相当于b,left最小,相当于a,再定义一个三角形计数器count。

保持p不动,判断left和right指向的元素之和与p的大小关系,若和大于p指向的元素,那么对于left、right、p指向的元素构成的三元组是能构成三角形的,同时,以right为基准,left到right之间的元素均大于left指向的元素,由单调性可知,left到right之间的元素与right相加的和也一定大于p指向的元素,那么count就要加上right - left,再将right向左移动一位;若left与right的和小于或等于p指向的元素,那么以left为基准,right左边的值均小于right指向的值,由单调性可知,left与right左边的值相加的结构也一定会小于p指向的元素,此时就没有三元组能构成三角形,要将left向右移动一位,继续判断。当right<=left时,p左边的元素全部判断完成,此时就要让p向左移动一位,继续新一轮的判断。

流程图、代码如下:

java">    public int triangleNumber(int[] nums) {Arrays.sort(nums);int n = nums.length;int p = n - 1;int count = 0;while (p > 1) {int left = 0;int right = p - 1;while (left < right) {if (nums[left] + nums[right] > nums[p]) {count += (right - left);right--;} else {left++;}}p--;}return count;}

 希望读者能指点一二!


http://www.ppmy.cn/news/1537517.html

相关文章

ArkTS基本语法详解

ArkTS基本语法详解&#xff1a; ArkTS页面布局 数据类型 条件判断 数组 ForEach循环遍历 List ListItem组件详解 官方文档 &#xff1a; https://developer.harmonyos.com/cn/develop/arkts/ ArkTS 是 HarmonyOS 优选的主力应用开发语言。 ArkTS 围绕应用开发在 TypeScript &…

Mac 需要杀毒软件?

大部分 mac用户普遍认为 Apple mac 不受病毒和恶意软件的影响。这导致许多 Mac 用户误以为无需为 Mac 安装防病毒软件&#xff0c;但事实并非如此。 在这篇文章中&#xff0c;将深入探讨 Mac 安全性的细节&#xff0c;探索针对 Apple 设备的恶意软件类型&#xff0c;并为您…

Python计算生态概述

Python计算生态涵盖网络爬虫、数据分析、文本处理、数据可视化、图形用户界面、机器学习、Web 开发、网络应用开发、游戏开发、虚拟现实、图形艺术等多个领域&#xff0c;为各个领域的Python使用者提供了极大便利。 网络爬虫是一种按照一定的规则&#xff0c;自动从网络上抓取…

洗衣店订单处理:Spring Boot系统的优势

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…

基于逻辑回归实现乳腺癌预测

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

【C++】C++入门基础

一. 第一个C程序 #include<iostream> using namespace std;int main() {cout << "hello world" << endl;return 0; } 二.命名空间 1.namespace的价值 在C/C中&#xff0c;变量、函数和后⾯要学到的类都是⼤量存在的&#xff0c;这些变量、函数…

Github 2024-10-08 Python开源项目日报Top10

根据Github Trendings的统计,今日(2024-10-08统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目10JavaScript项目1系统设计指南 创建周期:2507 天开发语言:Python协议类型:OtherStar数量:241693 个Fork数量:42010 次关注人数…

前端面试:项目细节重难点问题分享(18)

更多详情&#xff1a;爱米的前端小笔记&#xff08;csdn~xitujuejin~zhiHu~Baidu~小红shu&#xff09;同步更新&#xff0c;等你来看&#xff01;都是利用下班时间整理的&#xff0c;整理不易&#xff0c;大家多多&#x1f44d;&#x1f49b;➕&#x1f914;哦&#xff01;你们…