【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数
611. 有效三角形的个数
https://leetcode.cn/problems/valid-triangle-number/
题目描述:
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

解题思路:
本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边
题目给我们nums是乱序的,如果我们一个个abc去实验就是会超时(时间复杂度O^3)
当我们将sort排序一下,这样的话假设a<b<c的情况下,我们就只要去判断a+b>c是否成立!
这里我们遍历每个c(从后往前),这样时间复杂度就变成了N^2+NlogN也就是N^2
解题代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//假设a<b<cint num=0;int n=nums.size();for(int i=n-1;i>=2;i--){int left=0;int right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){num+=(right-left);right--;}else{left++;}}}return num;}
};
剑指 Offer 57. 和为s的两个数字
剑指 Offer 57. 和为s的两个数字
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
题目描述:
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

解题思路:
首先本题是升序数组,这里如果我们用暴力的话会超时
这里我们使用双指针,我们让一个指向头left一个指向尾right,这里left、right和target会有三种关系
我们假设sub=right-left
第一种情况很显然直接返回就好了我们来研究一下第二种和第三种情况:
解题代码:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();int left=0;int right=n-1;while(nums[right]>target){right--;}while(left<right){int sub=target-nums[right];if(sub==nums[left]){return {nums[left],nums[right]};}else if(sub>nums[left]){left++;}else//sub<nums[left]{right--;}}return {-1,-1};}
};
相关文章:
【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数 611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/ 题目描述: 给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。 解题思路: 本题是一个关于三角形是否能成立…...
通过 kk 创建 k8s 集群和 kubesphere
官方文档:多节点安装 确保从正确的区域下载 KubeKey export KKZONEcn下载 KubeKey curl -sfL https://get-kk.kubesphere.io | VERSIONv3.0.7 sh -为 kk 添加可执行权限: chmod x kk创建 config 文件 KubeSphere 版本:v3.3 支持的 Kuber…...
感觉和身边其他人有差距怎么办?
虽然清楚知识需要靠时间沉淀,但在看到自己做不出来的题别人会做,自己写不出的代码别人会写时还是会感到焦虑怎么办? 你是否也因为自身跟周围人的差距而产生过迷茫,这份迷茫如今是被你克服了还是仍旧让你感到困扰? 下…...
【C语言基础】宏定义的用法详解
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
微服务系列文章之 SpringBoot 最佳实践
Spring Boot 是一种广泛使用且非常流行的企业级高性能框架。 以下是一些最佳实践和一些技巧,我们可以使用它们来改进 Spring Boot 应用程序并使其更加高效。 Spring Boot 的四大核心 1、自动配置 针对很多Spring应用程序和常见的应用功能,Spring Boo…...
C++并发多线程--std::async、std::packaged_task和std::promise的使用
目录 1--std::async的使用 2--std::packaged_task的使用 3--std::promise的使用 1--std::async的使用 std::async用于启动一个异步任务,并返回一个std::future对象;std::future对象里含有异步任务线程入口函数的结果; std::launch::deferr…...
opencv-目标追踪
import argparse import time import cv2 import numpy as np# 配置参数 ap argparse.ArgumentParser() ap.add_argument("-v", "--video", typestr,help"path to input video file") ap.add_argument("-t", "--tracker", …...
【数据结构】 单链表面试题讲解
文章目录 引言反转单链表题目描述示例:题解思路代码实现: 移除链表元素题目描述:示例思路解析: 链表的中间结点题目描述:示例:思路解析代码实现如下: 链表中倒数第k个结点题目描述示例思路解析&…...
C++ string类的模拟实现
模拟实现string类不是为了造一个更好的轮子,而是更加理解string类,从而来掌握string类的使用 string类的接口设计繁多,故而不会全部涵盖到,但是核心的会模拟实现 库中string类是封装在std的命名空间中的,所以在模拟…...
Qt实现简单的漫游器
文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。 QOpenGLWidget 提供了三个便捷的虚函数,可以重载,用来重新实现典型的OpenGL任务: paintGL:渲染…...
【c语言】文件操作
朋友们,大家好,今天分享给大家的是文件操作的相关知识,跟着我一起学习吧!! 🎈什么是文件 磁盘上的文件是文件。 但是在程序设计中,我们一般谈的文件有两种:程序文件、数据文件 程序文…...
【Unity】坐标转换经纬度方法(应用篇)
【Unity】坐标转换经纬度方法(应用篇) 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法,理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法(原理篇),在实际使用中,…...
element时间选择器el-date-picter使用disabledDate指定禁用的日期
需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…...
出学校干了 5 年外包,已经废了
如果不是女朋友和我提分手,我估计现在还没醒悟 本科大专,17年通过校招进入某软件公司做测试,干了接近5年的功能。 今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经…...
day-23 代码随想录算法训练营(19)part09
669.修剪二叉搜索树 思路一:根据二叉搜索树的特性进行中间值与去区间值判断,有三种情况:1.在区间中,所以左右子树都可能在区间中; 2.在区间外面的左侧,必然只有右子树可能存在区间中;3.在区间外…...
JVM编译优化
即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...
vue浏览器插件安装-各种问题
方法1:vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址: Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源(推荐使用nrm,这一步是为…...
maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven
Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 Maven项目对象模型(POM),可以通过一小段描述信息来管理项目的构建,报告和文档的…...
Mac鼠标增强工具Smooze Pro
Smooze Pro是一款Mac上的鼠标手势增强工具,可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作,包括单指、双指、三指和四指手势,并且可以自定义每种手势的功能。例如,您可以使用单指向下滑动手势来启动Expos视…...
数据结构-单链表(C语言简单实现)
简介 以顺序结构进行数据存储时,它的特点就是可以用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的,这些数据可以存在内存未被占用的任意位置。它也是有缺点的,就是在插入和删除时需要移…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...



