【优选算法】——双指针(下篇)!

🌈个人主页:秋风起,再归来~
🔥系列专栏:C++刷题算法总结
🔖克心守己,律己则安
目录
1、有效三角形的个数
2、查找总价值为目标值的两个商品
3、三数之和
4、四数之和
5、完结散花
1、有效三角形的个数
题目链接
https://leetcode.cn/problems/valid-triangle-number/description/
给定一个包含非负整数的数组
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、 暴力解法:我们可以很轻松的想到枚举所有的三条变,判断它们是否可以组成三角形,记录有效三角形的个数即可。不过n^3的时间复杂度会超出时间限制!
class Solution {
public:int triangleNumber(vector<int>& nums) {int len=nums.size(),count=0;for(int a=0;a<len-2;a++){for(int b=a+1;b<len-1;b++){for(int c=b+1;c<len;c++){if(nums[a]+nums[b]>nums[c]&&nums[a]+nums[c]>nums[b]&&nums[b]+nums[c]>nums[a]) count++;}}}return count;}
};

2、更优解法:我们先将数组排序,因为判断三个数是否可以构成三角形只需要比较较小两边之和是否大于第三边即可。
3、排序后,nums[len-1]的位置就是最大值,我们先用max固定一端,right固定在max左侧,left固定在起点。

4、判断nums[left]+nums[right]是否大于nums[max]
a、如果小于,left++
b、如果大于,count+=(right-left ),固定max和right两边后,left是right之后最小的一边。如果最小的一边加上right都大于max,那其后的边一定可以构成三角形。所以我们就没有必要进行无意义的枚举。
c、此时固定max和right的情况已近枚举完成,那我们就让right--。
class Solution {
public:int triangleNumber(vector<int>& nums) {int max=nums.size()-1,count=0;//排序sort(nums.begin(),nums.end());//固定枚举maxwhile(max>=2){//固定枚举rightint right=max-1;int left=0;while(left<right){if(nums[left]+nums[right]>nums[max]) {count+=(right-left);right--;}else left++;}max--;}return count;}
};
2、查找总价值为目标值的两个商品
题目链接
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
购物车内的商品价格按照升序记录于数组
price。请在购物车中找到两个商品的价格总和刚好是target。若存在多种情况,返回任一结果即可。示例 1:
输入:price = [3, 9, 12, 15], target = 18 输出:[3,15] 或者 [15,3]示例 2:
输入:price = [8, 21, 27, 34, 52, 66], target = 61 输出:[27,34] 或者 [34,27]
由于题目比较简单,直接上代码了!
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0,right=price.size()-1;while(left<right){if(price[left]+price[right]<target) left++;else if(price[left]+price[right]>target) right--;else {//走隐式类型转换return {price[left],price[right]};}}return {-1,-1};}
};
3、三数之和
题目链接
https://leetcode.cn/problems/3sum/description/
给你一个整数数组
nums,判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k,同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。示例 2:
输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。示例 3:
输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。
解题思路:
1、这个题目的整体思路可以转化为两数之和==target,和上一道题目相似,不过在细节上还是有些不同。
2、排序后,我们定义target在len-1的位置,left=0,right=target-1。判断nums[left]+nums[right]==-nums[target]就可以了。
>不过,这里还涉及到去重的问题:
我们找到一个三元组后,left++,right--
a.如果left==left--,那么我们找到的下一个三元组必然和前一个相等!(因为left和target固定了)
b.同理,如果right==right+1,那么我们找到的下一个三元组必然和前一个相等!
c.再有,如果target==target+1,我们在下一个区间查找的所有情况再上一个区间都查找过了!
d.所以这三种情况我们都要跳过相同的元素来进行去重操作!

解题代码:
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());//排序int len=nums.size();for(int target=len-1;target>=2;){if(nums[target]<0) break;//小优化int left=0,right=target-1;while(left<right){if(nums[left]+nums[right]<-nums[target]) left++;else if(nums[left]+nums[right]>-nums[target]) right--;else {ret.push_back({nums[left++],nums[right--],nums[target]});//去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重target--;while(target>=2&&nums[target]==nums[target+1]) target--;}return ret;}
};
4、四数之和
题目链接
https://leetcode.cn/problems/4sum/description/
给你一个由
n个整数组成的数组nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]](若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2:
输入:nums = [2,2,2,2,2], target = 8 输出:[[2,2,2,2]]
解题思路:
1、这道题目的整体思路和三数之和差不多,我们可以把上一题理解为两数之和==target(0) - 一个数(自己固定枚举)。
2、而这道题目无非就是再三数之和的基础上,再多枚举一个数而已!
解题代码:
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int len=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int d=len-1;d>=3;){if(target<0&&nums[0]>=0) break;//小优化//三数之和逻辑for(int c=d-1;c>=2;){long long tmp=(long long)target-nums[c]-nums[d];int left=0;int right=c-1;while(left<right){if(nums[left]+nums[right]<tmp) left++;else if(nums[left]+nums[right]>tmp) right--;else{ret.push_back({nums[left++],nums[right--],nums[c],nums[d]});//left,right去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//c去重c--;while(c>=2&&nums[c]==nums[c+1]) c--;}//d去重d--;while(d>=3&&nums[d]==nums[d+1]) d--;}return ret;}
};
5、完结散花
好了,这期的分享到这里就结束了~
如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~
我们下期不见不散~~
相关文章:
【优选算法】——双指针(下篇)!
🌈个人主页:秋风起,再归来~ 🔥系列专栏:C刷题算法总结 🔖克心守己,律己则安 目录 1、有效三角形的个数 2、查找总价值为目标值的两个商品 3、三数之和 4、四数之和 5、完结散花 1、有…...
C#中函数重载的说明
一.函数重载的基本概念 C# 中的函数重载是指在同一个类中定义多个同名的函数,但这些函数的参数类型、参数个数、参数顺序等不同,以便适应不同的调用需求,增加代码的兼容性。 二.函数重载的作用 2.1定义多个相类似的函数,减少函…...
图论day56|广度优先搜索理论基础 、bfs与dfs的对比(思维导图)、 99.岛屿数量(卡码网)、100.岛屿的最大面积(卡码网)
图论day56|广度优先搜索理论基础 、bfs与dfs的对比(思维导图)、 99.岛屿数量(卡码网)、100.岛屿的最大面积(卡码网)) 广度优先搜索理论基础bfs与dfs的对比(思维导图)&…...
源码编译方式安装htppd软件
一.源码编译安装httpd软件 1.安装阿帕奇的依赖,安装apr软件,阿帕奇正常运行的环境这个环境就是apr。 2.安装apr-util软件,主要提供针对apr环境的管理工具, 3.安装阿帕奇软件即httpd软件。 如上图所示,就是三个软件的…...
MES制造执行系统原型图动端 Axure原型 交互设计 Axure实战项目
MES制造执行系统原型移动端 Manufacturing Execution System prototype MES制造执行系统原型图移动端是专门为制造执行系统设计的移动端是一个可视化的设计。用于展示和演示该系统在移动设备上的功能和界面。通过原型图,可以清晰地了解制造执行系统在移动端的各个…...
flutter 仿淘宝推荐二级分类效果
先看效果 一开始 用的PageView 做的, 然后重写PageScrollPhysics一顿魔改, 最后发现还是有一些小bug。 后面又想到pageview 能做,listview肯定也能做,最后用ListView加GridView 把功能实现了。 listview 实现pageview 的分页滑动…...
报错 - LangChain AgentExecutor - ‘function‘ object has no attribute ‘get‘
使用 AgentExecutor 调用了使用两个 tool 的agent,报一下错误: 如果 agent 只使用 一个tool,没有报错 File "/Users/xx/miniconda3/envs/env1/lib/python3.11/site-packages/pydantic/_internal/_validators.py", line 44, in sequ…...
【DIY小记】通过降低电压和Process Lasso工具优化CPU超频表现
又到了创作纪念日,秉承着笔耕不辍的理念,笔者还是继续分享一下DIY日常。 在上一篇文章当中,笔者介绍了一些作为新手小白超频CPU和NVIDIA显卡的经验。今天又有了更新,笔者通过降低CPU工作电压,并且结合Process Lasso对…...
3、Docker搭建MQTT及Spring Boot 3.x集成MQTT
一、前言 本篇主要是围绕着两个点,1、Docker 搭建单机版本 MQTT(EMQX),2、Spring Boot 3.x 集成 MQTT(EMQX); 而且这里的 MQTT(EMQX)的搭建也只是一个简单的过程&#x…...
六种定时任务记录
1、java自带的Timer Timer是java中自带的类。 优点:使用简单,缺点是当添加并执行多个任务时,前面任务的执行用时和异常将影响到后面任务。 Timer timer new Timer();timer.schedule(new TimerTask() {int i 0;Overridepublic void run() …...
Dos下编译环境搭建和C运行程序生成
文章目录 前言一、需要准备的Tool二、搭建步骤 前言 因为工作需要,需要搭建个Dos下的编译环境来进行Code App开发,如下记录下搭建过程。 一、需要准备的Tool 编译环境:Win10/win11 编译工具: DOSBox0.74 Turboc2.7z 二、搭建步骤 1.双击压…...
【MySQL】入门篇—SQL基础:数据查询语言(DQL):复杂的SELECT语句
在实际应用中,复杂的SELECT语句可以帮助我们从多个表中提取相关信息,进行数据分析,生成报告,甚至进行数据挖掘。 掌握复杂的SELECT语句对于数据分析师、数据库管理员和开发者来说是必不可少的技能。 应用场景: 多表查…...
Appium环境搭建、Appium连接真机
文章目录 一、安装Android SDK二、安装Appium-desktop三、安装Appium Inspector 一、安装Android SDK 首先需要安装jdk,这里就不演示安装jdk的过程了 SDK下载地址:Android SDK 下载 1、点击 Android SDK 下载 -> SKD Tools 2、选择对应的版本进行下…...
【X线源】关于滨松MCS2软件的说明
【X线源】关于滨松MCS2软件的说明 1.软件背景2.MCS2界面3.MCS2操作4.常见问题 1.软件背景 滨松为了方便客户将滨松MFX集成进自己的系统,滨松提供了MFX二次开发相关的信息和Demo代码。参考博客说明: 【X线源】关于滨松MFX二次开发demo示例简介 https://…...
【深度学习代码调试2】环境配置篇(中) -- 列出conda环境中所有env的pytorch版本
【深度学习代码调试2】环境配置篇(中) -- 列出conda环境中所有env的pytorch版本 写在最前面如何检查所有 Conda 环境中的 PyTorch 版本(并重点提示 PyTorch 1.7.1 版本)1. 列出所有 Conda 环境2. 检查每个环境中的 PyTorch 版本方…...
C语言运算符和表达式
1.C语言赋值运算符实例讲解 C 使用运算符(operator)来代表算术运算。例如,运算符可以使它两侧的值加在一起。如果您觉得术语“运算符”听起来比较奇怪,那么请您记住那些东西总得有个名称。与其被称之为“那些东西”或“数学符号”,被称之为“…...
RetinaNet 分类头和回归头的网络结构分析
RetinaNet 是由 Facebook AI Research(FAIR)在 2017 年提出的一种高效的一阶段(one-stage)目标检测算法。相比于两阶段(two-stage)方法,RetinaNet 通过引入 Focal Loss 解决了类别不平衡问题&am…...
app测试有哪些内容?广东深圳软件测试机构推荐
随着智能手机的普及,手机应用app越来越多,因此,企业为了更好的保证用户留存率,开发完app之后必须进行app测试。一个成功的app,软件测试是必不可少的一步,那么app测试需要进行哪些测试内容呢?深圳又有哪些靠…...
新乡医学院第一附属医院启动巨额医疗设备整体维保招标
鉴于项目本身金额巨大,又恰逢省委巡视组进驻期间,该项目备受瞩目,在业内和省内医疗圈引起了极大轰动。全国影响力最大、实力最强的企业全部参与其中,民营企业上海柯渡医疗、上海昆亚医疗以其创新的服务模式和高效的管理机制备受关注;央企通用技术集团凯思轩达医疗科技凭借雄厚的…...
Linux——综合实用操作
目录 IP与主机 ping命令 wget命令 curl命令 端口:设备与外界通讯交流的出入口 进程管理 Linux top命令Windows 任务管理器 磁盘信息监控 df iostat 网络状态监控 sar -n DEV命令 环境变量 上传,下载 压缩 解压tar,zipÿ…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...




