力扣(LeetCode)611. 有效三角形的个数(Java)

White graces:个人主页

🙉专栏推荐:Java入门知识🙉

🐹今日诗词:雾失楼台,月迷津渡🐹


⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏

⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏


题目描述

题目链接: 611. 有效三角形的个数

题目分析

正常思路(暴力解法)

遍历所有可能情况, 判断出能够成三角形的情况, 并记录下来

缺点: 复杂度较高, 并且容易超时

双指针算法

三角形: 任意两边之和大于第三边,

如果我们对数组进行排序, 只需要看最小的值大于第三边就可以了

因此我们固定最大值, 移动较小值

比如2   2   3    4, 固定最大值, 可以构成三个三角形,

那么如何遍历出这三种情况呢?

我们定义三个指针, left, right, cur

固定cur指针, 移动左右两个指针

right = 3时有两张情况, 2 3 4(第一个2),2 3 4(第二个2)

此时记录三角形的个数, 个数等于  right - left ,然后继续right--继续遍历

右边指针移动的时机

符合三角形判断条件移动右指针左移: 也就是左右指针对应元素和大于cur元素

右指针移动的时机

不符合三角形判断条件移动右指针左移

编写代码

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        // 记录个数
        int result = 0;

        for (int cur = nums.length - 1; cur >= 2; cur--) {
            int left = 0;
            int right = cur - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[cur]) {
                    // 符合三角形判断条件, right--, 继续看还有没有符合的
                    result += right - left;
                    right--;
                } else {
                    // 说明两边和小于第三边, left+1, 加过之后看两边能不能大于第三边
                    left++;
                }
            }
        }
        return result;
    }
}

复杂度分析

美图分享

✨🎆谢谢你的阅读和耐心!祝愿你在编程的道路上取得更多的成功与喜悦!"🎆✨🎄

⭐️点赞收藏加关注,学习知识不迷路⭐️

🎉✔️💪🎉✔️💪🎉✔️💪🎉✔️💪🎉

👍😏⛳️点赞☀️收藏⭐️关注😏👍

👍😏⛳️点赞☀️收藏⭐️关注😏👍

👍😏⛳️点赞☀️收藏⭐️关注😏👍

🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️

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

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

相关文章

Mac Nginx 前端打包部署

安装homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 安装Nginx brew install nginx nginx相关命令 nginx启动命令&#xff1a;nginx nginx -s reload #重新加载配置 nginx -s reopen #重启 nginx -s stop #…

利用VMware workstation pro 17安装 Centos7虚拟机以及修改网卡名称

通过百度网盘分享的文件&#xff1a;安装虚拟机必备软件 链接&#xff1a;https://pan.baidu.com/s/1rbYhDh8x1hTzlSNihm49EA?pwdomxy 提取码&#xff1a;omxy 123网盘 https://www.123865.com/s/eXPrVv-UsKch 提取码:eNcy 先自行安装好VMware workstation pro 17 设置虚拟机…

《实时流计算系统设计与实现》-Part 2-笔记

做不到实时 做不到实时的原因 实时计算很难。通过增量计算的方式来间接获得问题的&#xff08;伪&#xff09;实时结果&#xff0c;即使这些结果带有迟滞性和近似性&#xff0c;但只要能够带来尽可能最新的信息&#xff0c;那也是有价值的。 原因可分成3个方面&#xff1a; …

《C陷阱与缺陷》

文章目录 1、【词法陷阱】1.1 符号与组成符号间的关系1.1 与 1.3 y x/*p 与 y x/(*p)&#xff0c;a-1 与 a - 1 与 a -1, 老版本编译器的处理是不同的&#xff0c;严格的ANSI C则会报错1.4 十进制的 076&#xff0c;会被处理为八进制&#xff0c;ANSI C禁止这种用法&#x…

初阶C++之C++入门基础

大家好&#xff01;欢迎来到C篇学习&#xff0c;这篇文章的内容不会很难&#xff0c;为c的引入&#xff0c;c的重点内容将在第二篇的文章中讲解&#xff0c;届时难度会陡然上升&#xff0c;请做好准备&#xff01; 我们先看网络上的一个梗&#xff1a;21天内⾃学精通C 好了&am…

Maven 构建项目

Maven 是一个项目管理和构建工具&#xff0c;主要用于 Java 项目。它简化了项目的构建、依赖管理、报告生成、发布等一系列工作。 构建自动化&#xff1a;Maven 提供了一套标准化的构建生命周期&#xff0c;包括编译、测试、打包、部署等步骤&#xff0c;通过简单的命令就可以执…

Android中桌面小部件的开发流程及常见问题和解决方案

在Android中&#xff0c;桌面小部件&#xff08;App Widget&#xff09;是应用程序可以在主屏幕或其他地方显示的一个可视化组件&#xff0c;提供简化信息和交互功能。Android桌面小部件的framework为开发者提供了接口&#xff0c;使得可以创建和更新小部件的内容。以下是Andro…

opencv(c++)----图像的读取以及显示

opencv(c)----图像的读取以及显示 imread: 作用&#xff1a;读取图像文件并将其加载到 Mat 对象中。参数&#xff1a; 第一个参数是文件路径&#xff0c;可以是相对路径或绝对路径。第二个参数是读取标志&#xff0c;比如 IMREAD_COLOR 表示以彩色模式读取图像。 返回值&#x…

马斯克万卡集群AI数据中心引发的科技涟漪:智算数据中心挑战与机遇的全景洞察

一、AI 爆发重塑数据中心格局 随着AI 技术的迅猛发展&#xff0c;尤其是大模型的崛起&#xff0c;其对数据中心产生了极为深远的影响。大模型以其数以亿计甚至更多的参数和对海量数据的处理需求&#xff0c;成为了 AI 发展的核心驱动力之一&#xff0c;同时也为数据中心带来了…

搭建Python2和Python3虚拟环境

搭建Python3虚拟环境 1. 更新pip2. 搭建Python3虚拟环境第一步&#xff1a;安装python虚拟化工具第二步&#xff1a; 创建虚拟环境 3. 搭建Python2虚拟环境第一步&#xff1a;安装虚拟环境模块第二步&#xff1a;创建虚拟环境 4. workon命令管理虚拟机第一步&#xff1a;安装扩…

C语言的内存函数(文章后附gitee链接,模拟实现函数)

之前我们已经讲解过了字符型数据的一类字符串函数&#xff0c; 现在我们来讨论字符型以外的数据处理。 1&#xff1a;memcpy 的使用和模拟实现 void * memcpy ( void * destination, const void * source, size_t num )&#xff1b; 注意&#xff1a; 1&#xff1a;函数memcp…

FPGA/Verilog,Quartus环境下if-else语句和case语句RT视图对比/学习记录

基本概念 RTL&#xff08;Register - Transfer - Level&#xff09;视图&#xff1a;是一种硬件描述语言的抽象层次&#xff0c;用于描述数字电路中寄存器之间的数据传输和操作。在这个层次上&#xff0c;可以看到电路的基本结构&#xff0c;如寄存器、组合逻辑、多路复用器等…

react的创建与书写

一&#xff1a;创建项目 超全面详细一条龙教程&#xff01;从零搭建React项目全家桶&#xff08;上篇&#xff09; - 知乎 1.创建一个文件夹&#xff0c;shift鼠标右键选择在此处打开powershell 2.为了加速npm下载速度&#xff0c;先把npm设置为淘宝镜像地址。 npm config s…

【动态规划】两个数组的 dp 问题

1. 最长公共子序列 1143. 最长公共子序列 状态表示&#xff1a; dp[i][j] 表示 s1 的 0 ~ i 区间和 s2 的 0 ~ j 区间内所有子序列中&#xff0c;最长公共子序列的长度 状态转移方程&#xff1a; 当 s1[i] 和 s2[j] 相等时&#xff0c;那么最长公共子序列一定是以这两个位置…

【计算机网络】【传输层】【习题】

计算机网络-传输层-习题 文章目录 10. 图 5-29 给出了 TCP 连接建立的三次握手与连接释放的四次握手过程。根据 TCP 协议的工作原理&#xff0c;请填写图 5-29 中 ①~⑧ 位置的序号值。答案技巧 注&#xff1a;本文基于《计算机网络》&#xff08;第5版&#xff09;吴功宜、吴英…

nacos集群部署与配置

Nacos集群模式 1. 预备环境准备 请确保是在环境中安装使用: 64 bit OS Linux/Unix/Mac&#xff0c;推荐使用Linux系统。64 bit JDK 1.8&#xff1b;下载. 配置。Maven 3.2.x&#xff1b;下载. 配置。3个或3个以上Nacos节点才能构成集群 ubuntu中假如没安装jdk&#xff0c;则…

Python学习从0到1 day26 第三阶段 Spark ③ 数据计算 Ⅱ

目录 一、Filter方法 功能 语法 代码 总结 filter算子 二、distinct方法 功能 语法 代码 总结 distinct算子 三、SortBy方法 功能 语法 代码 总结 sortBy算子 四、数据计算练习 需求&#xff1a; 解答 总结 去重函数&#xff1a; 过滤函数&#xff1a; 转换函数&#xff1a; 排…

Jmeter基础篇(23)TPS和QPS的异同

前言 这是一篇性能测试指标的科普文章哦&#xff01; TPS和QPS是同一个概念吗&#xff1f; TPS&#xff08;Transactions Per Second&#xff09;和QPS&#xff08;Queries Per Second&#xff09;虽然都是衡量系统性能的指标&#xff0c;但是它们并不是同一个概念。这两个各…

IEC60870-5-104 协议源码架构详细分析

IEC60870-5-104 协议源码架构 前言一、资源三、目录层级一二、目录层级二config/lib60870_config.hdependencies/READMEexamplesCMakeLists.txtcs101_master_balancedcs104_client_asyncmulti_client_servertls_clienttls_server说明 make这些文件的作用是否需要导入这些文件&a…

机器学习在网络安全中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 机器学习在网络安全中的应用 机器学习在网络安全中的应用 机器学习在网络安全中的应用 引言 机器学习概述 定义与原理 发展历程 …