使用双指针解决问题题集(二)

1. 有效三角形的个数

给定一个包含非负整数的数组 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. 首先固定数组中最大的数。
  2. 在最大的数的左半边区间使用双指针算法,快速统计符合要求的三元组个数。
    如图:
    在这里插入图片描述
    在这里插入图片描述
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//优化数组int size = nums.size();int count = 0;for(int i =size-1;i>=2;i--){int left = 0;int right = i-1;while(left <right){if(nums[left]+nums[right]>nums[i]){count += right-left;right--;}else{left++;}}}return count;}
};

时间复杂度为: O(N2)

2. 查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 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]

提示:

1 <= price.length <= 10^5 1 <= price[i] <= 10^6 1 <= target <= 2*10^6

题解: 这道题目也是利用单调性和双指针算法来解决。
思路:
1.首先使用双指针第一个(left)指向数组开始第二个(right)指向数组的结尾。
2.若两个指针指向数据值的和(sum) 大于target,则right–
3.若sum小于target, 则 left++
4. 若是 sum= target ,则返回结果
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int size = price.size();int left = 0;int right = size-1;while(left<right){int sum = price[left] + price[right];if(sum > target)right--;else if(sum<target)left++;elsereturn {price[left],price[right]};}return {-1,-1};}
};

时间复杂度为: O(N)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

set_input_delay的理解

1&#xff0c;set_input_delay约束理解 input_delay是指输入的数据到达FPGA的pad引脚时相对于时钟边沿的延迟有多大&#xff0c;单位是ns&#xff0c;数值可以是正&#xff0c;也可以是负。通过set_input_delay约束告诉编译器输入时钟和输入数据的相位关系。如下图所示假设时钟…

C语言猜数字游戏

用C语言实现猜数字游戏&#xff0c;电脑随机给出一个范围内的数字&#xff0c;用户在终端输入数字&#xff0c;去猜大小&#xff1b;对比数字&#xff0c;电脑给出提示偏大还是偏小&#xff1b;不断循环&#xff0c;直到正确 #include <stdio.h> #include <time.h>…

C++ Primer 总结索引 | 第十四章:重载运算与类型转换

1、C语言定义了 大量运算符 以及 内置类型的自动转换规则 当运算符 被用于 类类型的对象时&#xff0c;C语言允许我们 为其指定新的含义&#xff1b;也能自定义类类型之间的转换规则 例&#xff1a;可以通过下述形式输出两个Sales item的和&#xff1a; cout << item1 …

快速找出存(不存在)在某个(或多个)文件的文件夹

首先&#xff0c;需要用到的这个工具&#xff1a; 度娘网盘 提取码&#xff1a;qwu2 蓝奏云 提取码&#xff1a;2r1z 想要找出有下面这个文件存在的文件夹 切换到批量文件复制版块&#xff0c;快捷键Ctrl5 右侧&#xff0c;搜索添加 选定范围&#xff0c;勾选搜索文件夹、包…

重生奇迹mu套装大全

1.战士 汉斯的皮套装&#xff1a;冰之指环,皮护腿,皮盔,皮护手,皮靴,皮铠,流星槌 汉斯的青铜套装&#xff1a;青铜护腿,青铜靴,青铜铠 汉斯的翡翠套装&#xff1a;雷之项链,翡翠护腿,翡翠盔,翡翠铠,远古之盾 汉斯的黄金套装&#xff1a;火之项链,黄金护腿,黄金护手,黄金靴,…

Skywalking数据持久化与自定义链路追踪

学习本篇文章之前首先要了解一下Sky walking的基础知识 分布式链路追踪工具Skywalking详解 一&#xff0c;Sky walking数据持久化 Sky walking提供了es&#xff0c;MySQL等数据持久化方案&#xff0c;默认使用h2基于内存的数据库&#xff0c;重启之后数据即会丢失。 在实际工…

renren-fast开源快速开发代码生成器

简介 renrenfast框架介绍 renren-fast是一个轻量级的Spring Boot快速开发平台&#xff0c;能快速开发项目并交付.完善的XSS防范及脚本过滤&#xff0c;彻底杜绝XSS攻击实现前后端分离&#xff0c;通过token进行数据交互 使用流程 项目地址 https://gitee.com/renrenio/ren…

k8s部署skywalking(helm)

官方文档 官方文档说明&#xff1a;Backend setup | Apache SkyWalking官方helm源码&#xff1a;apache/skywalking-helm官方下载&#xff08;包括agent、apm&#xff09;:Downloads | Apache SkyWalking 部署 根据官方helm提示&#xff0c;选择你自己部署的方式&#xff0c…

【LAMMPS学习】八、基础知识(5.8)LAMMPS 中热化 Drude 振荡器教程

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

SpringBoot中HandlerInterceptor拦截器的构建详细教程

作用范围&#xff1a;拦截器主要作用于Spring MVC的DispatcherServlet处理流程中&#xff0c;针对进入Controller层的请求进行拦截处理。它基于Java的反射机制&#xff0c;通过AOP&#xff08;面向切面编程&#xff09;的思想实现&#xff0c;因此它能够访问Spring容器中的Bean…

如何解决3D模型变黑或贴图不显示的问题---模大狮模型网

在进行3D建模和视觉渲染时&#xff0c;经常会遇到模型表面变黑或贴图不显示的问题&#xff0c;这可能严重影响最终视觉效果的质量。这些问题通常与材质设置、光照配置或文件路径错误有关。本文将探讨几种常见原因及其解决方法&#xff0c;帮助3D艺术家和开发者更有效地处理这些…

TinyXML-2介绍

1.简介 TinyXML-2 是一个简单、小巧的 C XML 解析库&#xff0c;它是 TinyXML 的一个改进版本&#xff0c;专注于易用性和性能。TinyXML-2 用于读取、修改和创建 XML 文档。它不依赖于外部库&#xff0c;并且可以很容易地集成到项目中。 tinyXML-2 的主要特点包括&#xff1a…

回归预测 | Matlab实现基于CNN-SE-Attention-ITCN多特征输入回归组合预测算法

回归预测 | Matlab实现基于CNN-SE-Attention-ITCN多特征输入回归组合预测算法 目录 回归预测 | Matlab实现基于CNN-SE-Attention-ITCN多特征输入回归组合预测算法预测效果基本介绍程序设计参考资料 预测效果 基本介绍 【模型简介】CNN-SE_Attention结合了卷积神经网络&#xff…

武汉星起航:精准布局,卓越服务——运营交付团队领跑亚马逊

在全球电商浪潮中&#xff0c;亚马逊平台以其独特的商业模式和全球化的市场布局&#xff0c;吸引了无数商家和创业者的目光。在这个充满机遇的市场中&#xff0c;武汉星起航电子商务有限公司凭借其专业的运营交付团队&#xff0c;以其独特的五对一服务体系和精准的战略布局&…

Azure AKS日志查询KQL表达式

背景需求 Azure&#xff08;Global&#xff09; AKS集群中&#xff0c;需要查询部署服务的历史日志&#xff0c;例如&#xff1a;我部署了服务A&#xff0c;但服务A的上一个版本Pod已经被杀掉由于版本的更新迭代&#xff0c;而我在命令行中只能看到当前版本的pod日志&#xff…

Git推送本地项目到gitee远程仓库

Git 是一个功能强大的分布式版本控制系统&#xff0c;它允许多人协作开发项目&#xff0c;同时有效管理代码的历史版本。开发者可以克隆一个公共仓库到本地&#xff0c;进行更改后将更新推送回服务器&#xff0c;或从服务器拉取他人更改&#xff0c;实现代码的同步和版本控制。…

普洱茶泡多少茶叶才算淡茶?

普洱茶淡茶一般放几克茶叶&#xff0c;品深茶官网根据多年专业研究与实践结果&#xff0c;制定了淡茶冲泡标准。在冲泡普洱茶淡茶时&#xff0c;茶叶的投放量是关键因素之一。淡茶冲泡标准旨在保持茶汤的清爽口感&#xff0c;同时充分展现普洱茶的独特风味。 根据《品深淡茶冲…

题目:吃奶酪

问题描述&#xff1a; 解题思路&#xff1a; 枚举每种吃奶酪顺序&#xff0c;并计算其距离&#xff0c;选择最小的距离即答案。v数组&#xff1a;记录顺序。 注意点&#xff1a;1. 每次用于min的s需要重置为0。 2. 实数包括小数&#xff0c;所以结构体内x,y为double类型。 3. 第…

C++变量的作用域与存储类型

一 变量的作用域和存储类型 1 变量的作用域(Scope) 指在源程序中定义变量的位置及其能被读写访问的范围分为局部变量(Local Variable)和全局变量(Global Variable) 1&#xff09;局部变量(Local Variable) 在语句块内定义的变量 形参也是局部变量 特点&#xff1a; 生存期是…

Windows系统和unbtun系统连接usb 3.0海康可见MVS和红外艾睿相机

一.海康可见USB3.0工业面阵相机 海康usb相机需要去海康官网上下载对应系统的MVS客户端及SDK开发包 海康机器人-机器视觉-下载中心 选择Windows系统和unbtun&#xff08;我是linux aarch64,所以选择了对应压缩包解压&#xff09; Windows系统 1.双击安装包进入安装界面&…