双指针解题

验证回文数(验证回文数-CSDN博客)和判断在子序列(判断子序列-CSDN博客)已经在之前进行了计算,今天有三个新的双指针问题:

两数之和II—输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1  index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 

思路:

双指针的思想,nums是一个有序的数组 因此我们可以使用这个特性,即数据从小到大递增,创建连个指针left指向0,right指向数组末尾 若它们所指向的数据和为target,直接返回 ;否则若值小于target,则left++ 否则 right--;

 public int[] twoSum(int[] numbers, int target) {int left=0,right=numbers.length-1;while(left<right){int sum=numbers[left]+numbers[right];if(sum==target)return new int []{left+1,right+1};else if(sum<target)left++;elseright--;}return new int[0];
}

盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

思路:

最笨方法就是暴力解法:就是经过两次循环计算出所有的储水量,找出其中最大的并返回。但可能会超时

在这里我们可以使用双指针,left指向0,right指向height.length-1; 初始化res=0,表示当前的盛水量,使用Math.min(height[left],height[right])*(right-left)来计算盛水量,=并与res进行比较将较大真存在res中,然后移动left或right :若height[left]<=height[right],就left++ 否则right--(是因为每次都是有Math.min来计算,所以移动较短的哪一方,若移动较长的哪一方,盛水量肯定减少)直到left>=right

public int maxArea(int[] height) {int left=0,right=height.length-1;int res=0;while(left < right){int k=Math.min(height[left],height[right])*(right-left);if(k>res)res=k;if(height[left]<=height[right])left++;elseright--;}return res;
}

三数之和

在看三数之和之前,可以看看两数之和

两数之和:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

思路:

  第一种:暴力解法 ,循环求解
public int[] twoSum(int[] nums, int target) {for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if(nums[i]+nums[j]==target)return new int []{i,j};}}return new int [0];
}
第二种:哈希算法

  创建一个hashmap存储数据和其对应的下标,刚开始时hashmap为空,循环遍历数组for(int i=0;i<nums.length;i++) 若hashmap中包含target-nums[i] 则返回其下标和i 否则就将其加入到hashmap中(这里我刚开始不懂,此时hashmap为空怎么去寻找数据?为target是由两数在组成的,比如9=2+7,第一次访问2,map中找不到7,将2加入到map中,当访问7时就可以在map中找到2 )

public int[] twoSum(int[] nums, int target) {hashMap<Integer> map=new HashMAp<>();for(int i=0;i<nums.length;i++){if(map.containsKey(target-nums[i]){return new int[]{map.get(target-nums[i],i};hashmap.put(nums[i],i);}return new int nums[0];
}

三数之和解题

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != 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、将三数之和变成一个数固定的两数之和

2、如何保证元素不重复??

     首先需要对数组进行排序Ayyays.sort(nums),这样就变成不递减的数组

     然后在进行遍历的过程中需要注意 此时遍历的数不能和它的前面一个数相同

   最后可以借鉴有序数组的两数之和进行寻找

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list=new AyyayList<List<Integer>>();int first=0;Arrays.sort(nums); // 进行排序for(first=0;first<nums.length;first++){//固定第一个数if(first>0 && nums[first]==nums[first-1]) //此时遍历的数不能和它的前面一个数相同,否则会出现重复return continue;  int target=0-nums[i]; //其余两数之和int thrid=nums.length-1; //第三个指针指向数组末尾for(int second=first+1; second<nums.length;second++){if(second>first+1 && nums[second]==nums[second-1])continue;while(second<thrid && nums[second]+nums[thrid]>target) //因为此时是从小到大排序的 ,所以当nums[second]+nums[thrid]不大于target就有可能找到那个数了thrid--;if(second==thrid)break;if(nums[second]==nums[thrid]){List<Integer> res=new AyyayList<>();res.add(nums[first]);res.add(nums[second]);res.add(nums[thrid]);list.add(res);}}}return list;
}

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

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

相关文章

ZL-GL-4离体组织灌流系统测试在恒温条件下离体标本的肌张拉力

简单介绍&#xff1a; 离体组织灌流系统为生理实验及药理实验提供恒温环境&#xff0c;在麦氏浴皿内加养液同时能通氧&#xff0c;测试在恒温条件下离体标本的肌张拉力&#xff0c;离体组织灌流系统具有进气口,配备微调固定器,省时省力,并提高了实验效率,同时可方便串联恒温供水…

【银河麒麟V10服务器OS-系统根分区扩容】指导教程手册

【银河麒麟V10服务器OS-系统根分区扩容】指导教程手册 环境信息&#xff1a;VMware虚拟软件16.0 首先查看KylinOS服务器版本&#xff1a;nkvers 备注&#xff1a; (Tercel) 版本是 V10 SP1 版本&#xff0c; (Sword) 版本是 V10 SP2 版本&#xff0c; (Lance) 版本是 V10 …

超声波清洗机哪家好一点?四大顶级高分超声波清洗机专业推荐

在日常生活中&#xff0c;我们每天都在与灰尘和污渍作斗争&#xff0c;尤其是对于那些细小、精密的物品&#xff0c;如眼镜。眼镜不仅是视力矫正的工具&#xff0c;更是我们个人形象的一部分。一副干净、明亮的眼镜可以让我们的视线更加清晰。因为保持眼镜的清洁是一件很重要的…

初始操作系统

概念&#xff1a; 1.系统资源的管理者&#xff1a;实质控制和管理整个计算机系统的硬件和软件资源&#xff0c;并合理地组织调度计算机地工作和资源的分配 2.向上层提供方便易用的服务&#xff1a;以提供给用户和其他软件方便接口和环境 封装思想&#xff1a;操作系统把一些丑…

进阶 RocketMQ - 消息存储-一张图掌握核心要点

看了很多遍源码整理的 一张图进阶 RocketMQ 图片&#xff0c;关于 RocketMQ 你只需要记住这张图&#xff01; 消息传递责任已移交至Broker&#xff0c;接下来如何处理&#xff1f;首先&#xff0c;我们需要确保消息的持久化&#xff0c;避免因宕机导致的数据丢失。那么&#xf…

电商API商品数据采集接口||助力电商企业采集商品大数据提高开发效率

提高开发效率&#xff1a;电商API接口允许不同的应用程序之间高效地进行交互&#xff0c;节省了大量的人力物力成本&#xff0c;使得开发者可以将更多时间和精力集中于自身的核心业务。 增加数据安全性&#xff1a;通过对数据进行安全加密&#xff0c;API接口实现了对数据的保护…

IP地址开启HTTPS方法

可以使用IP地址申请SSL证书&#xff0c;申请之前必须是公网IP地址&#xff0c;不支持内网IP地址申请。 申请过程需要确定IP地址外网可以访问&#xff0c;这里特别注意只是申请过程中可以访问。访问验证过程必须采取80端口、443端口两者选择1个&#xff0c;不可以用其它端口进行…

[C/C++]_[初级]_[在Windows和macOS平台上导出动态库的一些思考]

场景 最近看了《COM本质论》里关于如何设计基于抽象基类作为二进制接口,把编译器和链接器的实现隐藏在这个二进制接口中,从而使用该DLL时不需要重新编译。在编译出C接口时,发现接口名直接是函数名,比如BindNativePort,怎么不是_BindNativePort?说明 VC++导出的函数默认是使…

javaweb——js

JavaScript是一种网页脚本语言。JavaScript代码可以很容易的嵌入到HTML页面中。 js引入 JavaScript嵌入到HTML页面中 <body><script>alert("Hello JS")</script> </body>再HTML页面中插入外部脚本JavaScript <body><script src&…

三、基于图像分类预训练编码及图神经网络的预测模型 【框图+源码】

背景&#xff1a; 抽时间补充&#xff0c;先挖个坑。 一、模型结构 二、源码

【2023百度之星初赛】跑步,夏日漫步,糖果促销,第五维度,公园,新材料,星际航行,蛋糕划分

目录 题目&#xff1a;跑步 思路&#xff1a; 题目&#xff1a;夏日漫步 思路&#xff1a; 题目&#xff1a;糖果促销 思路&#xff1a; 题目&#xff1a;第五维度 思路&#xff1a; 题目&#xff1a;公园 思路&#xff1a; 新材料 思路&#xff1a; 星际航行 思路…

python项目中requirements.txt文件使用

由于之前用的技术栈是java&#xff0c;后续项目中需要逐渐用起python&#xff0c;但是很多地方只会用&#xff0c;没太了解过本质作用是什么&#xff0c;这里总结下 requirements.txt 一.作用 requirements.txt 文件是 Python 项目中常见的文件&#xff0c;用于列出项目所需…

MySQL的组成与三种log

MySQL由几块组成 连接器分析器优化器执行器 MySQL的三大log blog 作用&#xff1a; 用于主从同步与数据恢复 记录内容&#xff1a; 已经完成的 DML(数据操作语句)&#xff0c;主要是用于数据备份 redolog<重试日志> 作用&#xff1a; 崩溃恢复&#xff0c;用于事…

web项目规范配置(husky、eslint、lint-staged、commit)

背景&#xff1a; 团队开发为了保证提交代码格式统一&#xff0c;通常在进行代码提交的时候对暂存区代码进行校验&#xff0c;如没有通过eslint(本例使用eslint)校验&#xff0c;则不能提交到远端。 安装依赖 husky 、eslint 、prettier 、lint-staged npm install husky e…

计算机网络——在地址栏输入网址(URL)之后都发生了什么

网址&#xff0c;也叫域名&#xff0c;域名就像一个 IP 地址的可读版本&#xff0c;比如&#xff0c;百度的域名 www.baidu.com&#xff0c;他的 ip 是 110.242.68.3&#xff0c;输入 IP 一样可以跳转到百度搜索的页面&#xff0c;我想没有一个人没去记百度的 IP 吧。其实我们真…

数据挖掘实战-基于长短期记忆网络(LSTM)的黄金价格预测模型 | 97% 准确度

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

网络安全等级保护相关标准及发展

目录 等保标准 等保定级 发展 等保标准 2016年11月发布的《网络安全法》第二十一条提出“国家实行网络安全等级保护制度”。 等级保护标准体系&#xff1a; &#xff08;1&#xff09;安全等级类标准 主要包括GB/T 22240-2008《信息安全技术 信息系统安全保护等级保护定…

汽车IVI中控开发入门及进阶(二十五):CVBS视频流

前言: AHD和CVBS是两种视频格式,在车载摄像头中,有支持传统CVBS模拟视频的摄像头,也有支持新的高分辨率AHD格式的摄像头。 CVBS视频是经典的模拟视频格式,在视频经常显示在小型监视器上的车辆上仍然最受欢迎。如果想要车辆的最大分辨率,可选择AHD格式,即高分辨率模拟视…

启智CV机器人,ROS,ubuntu 20.04 【最后一步有问题】

资料&#xff1a; https://wiki.ros.org/kinetic/Installation/Ubuntu https://blog.csdn.net/qq_44339029/article/details/120579608 装VM。 装ubuntu20.04 desktop.iso系统。 装vm工具&#xff1a; sudo apt update sudo dpkg --configure -a sudo apt-get autoremove o…

守护任务用来防止资源冲突

背景&#xff1a;有三个任务&#xff0c;他们都需要操作数码管。每个任务对应三个数码管&#xff0c;共9个数码管。硬件上9个数码管的控制使用一套硬件完成。 策略&#xff1a;每个任务都往自己的队列里面发数据&#xff0c;单独建立一个监听任务&#xff1a;处理所有队列的数…