当前位置: 首页 > news >正文

【双指针遍历】N数之和问题

文章目录

      • 二数之和LC1
      • 三数之和LC15
      • 四数之和LC18
      • 最接近的三数之和LC16

二数之和LC1

题目链接

给定一个整数数组 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]

代码:

// 仅需一次for循环
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0; i < nums.length;i++){int cur = target - nums[i]; if(map.containsKey(cur)){int x = map.get(cur);return new int[]{x,i};}map.put(nums[i],i);}return new int[]{-1,-1}; }
}

三数之和LC15

题目链接

给你一个整数数组 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 。

代码:

class Solution {public List<List<Integer>> threeSum(int[] nums) {int len = nums.length;Arrays.sort(nums);List<List<Integer>> finalres = new ArrayList<>();for(int i = 0; i < len-2;i++){int cur = nums[i];int l = i+1;int r = len-1;while(l < r){int left = nums[l];int right = nums[r];int sum = cur+left+right;if(sum > 0){while(l<r&&nums[r]==right)r--;// 移动指针,并排除相同元素}else if(sum<0){while(l<r&&nums[l]==left)l++;// 移动指针,并排除相同元素}else{List<Integer> res = new ArrayList<>();res.add(cur);res.add(left);res.add(right);finalres.add(res);while(l<r&&nums[r]==right)r--;// 移动指针,并排除相同元素while(l<r&&nums[l]==left)l++;// 移动指针,并排除相同元素}}while(i<len-2&&nums[i+1]==cur)i++;}return finalres;}
}

四数之和LC18

题目链接

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n
a、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]]

代码:

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);// 先排序return nTargetSum(nums,0,4,target);// 从数组0下标开始找,找4个数}public List<List<Integer>> nTargetSum(int[] nums,int i,int needNum,long target){// if(needNum < 2){//     List<List<Integer>> res = new ArrayList<>();//     return res;// }if(needNum==2){// 转换为二数之和List<List<Integer>> res = new ArrayList<>();int l = i;int r = nums.length-1;while(l<r){int left = nums[l];int right = nums[r];if(left+right==target){List<Integer> re = new ArrayList<>(Arrays.asList(left,right));res.add(re);while(l<r && nums[r]==right)r--;while(l<r && nums[l]==left)l++;}else if(left+right>target){while(l<r && nums[r]==right)r--;}else if(left+right<target){while(l<r && nums[l]==left)l++;}}return res;}else{// 递归部分List<List<Integer>> finalr = new ArrayList<>();for(int j = i ; j < nums.length;j++){List<List<Integer>> sub = nTargetSum(nums,j+1,needNum-1,target-nums[j]);for(List<Integer> list:sub){list.add(nums[j]);finalr.add(list);}while(j+1 < nums.length && nums[j+1] == nums[j])j++;// 排序相同元素}return finalr;}}
}

最接近的三数之和LC16

题目链接

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。示例 2:
输入:nums = [0,0,0], target = 1
输出:0

代码:

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);// 注意先排序int finalresult = nums[0]+nums[1]+nums[2];int minCha = Integer.MAX_VALUE;int len = nums.length;for(int i = 0; i < nums.length-2;i++){// 第一个数指针int l = i+1;// 第2个数指针int r = nums.length-1;// 第3个数指针while(l<r){int mysum = nums[i]+nums[l]+nums[r];// 三数之和if(Math.abs(mysum-target) < minCha){// 更新答案finalresult = mysum;minCha = Math.abs(mysum-target);}if(mysum>target){r--;}else if(mysum<target){l++;}else{return target;}}}return finalresult;}
}

相关文章:

【双指针遍历】N数之和问题

文章目录 二数之和LC1三数之和LC15四数之和LC18最接近的三数之和LC16 二数之和LC1 题目链接 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对…...

Qt的QObject类

文章目录 QObject类如何在Qt中使用QObject的信号与槽机制&#xff1f;如何在Qt中使用QObject的属性系统&#xff1f;QObject的元对象系统如何实现对象的反射功能&#xff1f; QObject类 Qt的QObject类是Qt框架中的基类&#xff0c;它是所有Qt对象的父类。QObject提供了一些常用…...

【图论C++】链式前向星(图(树)的存储)

/*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记&#xff1a;转载需获得博主本人…...

16.PWM输入捕获示例程序(输入捕获模式测频率PWMI模式测频率和占空比)

目录 输入捕获相关库函数 输入捕获模式测频率 PWMI模式测频率和占空比 两个代码的接线图都一样&#xff0c;如下 测量信号的输入引脚是PA6&#xff0c;信号从PA6进来&#xff0c;待测的PWM信号也是STM32自己生成的&#xff0c;输出引脚是PA0。 需要配置电路连接图示如下&…...

pip version 更新

最近报了一个错&#xff1a; 解决办法&#xff1a; 在cmd输入“conda install pip” conda install pip 完了之后再输入&#xff1a; python -m pip install --upgrade pip ok....

Oracle - 多区间按权重取值逻辑

啰嗦: 其实很早就遇到过类似问题&#xff0c;也设想过&#xff0c;不过一致没实际业务需求&#xff0c;也就耽搁了&#xff1b;最近有业务提到了&#xff0c;和同事讨论&#xff0c;各有想法&#xff0c;所以先把逻辑整理出来&#xff0c;希望有更好更优的解决方案&#xff1b;…...

本次CTF·泰山杯网络安全的基础知识部分(二)

简记23年九月参加的泰山杯网络安全的部分基础知识的题目&#xff0c;随时补充 15&#xff08;多选&#xff09;网络安全管理工作必须坚持“谁主管、谁负责&#xff0c;谁运营、谁负责&#xff0c;谁使用、谁负责”的原则&#xff0c;和“属地管理”的原则 谁主管、谁负责&…...

MyBatis 映射文件(Mapper XML):配置与使用

MyBatis 映射文件&#xff08;Mapper XML&#xff09;&#xff1a;配置与使用 MyBatis是一个强大的Java持久化框架&#xff0c;它允许您将SQL查询、插入、更新和删除等操作与Java方法进行映射。这种映射是通过MyBatis的映射文件&#xff0c;通常称为Mapper XML文件来实现的。本…...

基于 SpringBoot 的大学生租房网站

文章目录 1 简介2 技术栈3 需求分析4 系统设计5 系统详细设计5.1系统功能模块5.2管理员模块5.3房主功能模块5.4用户功能模块 源码咨询 1 简介 本大学生租房系统使用简洁的框架结构&#xff0c;专门用于用户浏览首页&#xff0c;房屋信息&#xff0c;房屋评价&#xff0c;公告资…...

BL808学习日志-0-概念理解

一、主核心的介绍 1.三个核心在FREERTOS系统中相互独立&#xff0c;各负责各自的外设和程序&#xff1b;其中M0和LP核心在一个总线上&#xff0c;D0单独在一个总线上&#xff0c;两个总线使用AXI4.0(??)通讯&#xff1f; CPU0(M0)-E907架构&#xff0c;320MHz; CPU1(LP)-E9…...

CISSP学习笔记:业务连续性计划

第三章 业务连续性计划 3.1 业务连续性计划 业务连续性计划(BCP): 对组织各种过程的风险评估&#xff0c;发生风险的情况下为了使风险对组织的影响降至最小而定制的各种计划BCP和DRP首先考虑的人不受伤害&#xff0c;然后再解决IT恢复和还原问题BCP的主要步骤&#xff1a; 项…...

.NET Nuget包推荐安装

文章目录 前言通用WPFWebApiBlazor 前言 我这里的包主要是.NET Core的&#xff0c;.NET Framework可能不支持。 通用 Newtonsoft.Json&#xff1a;最常用的C#和Json对象互转的包。支持匿名对象&#xff0c;但是不支持Enum枚举类型&#xff0c;显示的是Enum的数值&#xff0c…...

【文献阅读】Pocket2Mol : 基于3D蛋白质口袋的高效分子采样 + CrossDocked数据集说明

Pocket2Mol: Efficient Molecular Sampling Based on 3D Protein Pockets code&#xff1a; GitHub - pengxingang/Pocket2Mol: Pocket2Mol: Efficient Molecular Sampling Based on 3D Protein Pockets 所用数据集 与“A 3D Generative Model for Structure-Based Drug Desi…...

TrustRadius 评论:为什么 Splashtop 优于 LogMeIn

在当今日益数字化的格局中&#xff0c;远程访问和远程支持工具不仅方便而且至关重要。无论对于居家办公人员&#xff0c;还是对于提供远程支持的 IT 专家&#xff0c;能够安全高效地访问远程系统已成为以技术为导向的日常生活的主要内容。 Splashtop 和 LogMeIn 是远程领域的两…...

【动态规划】动态规划经典例题 力扣牛客

文章目录 跳台阶 BM63 简单跳台阶扩展 JZ71 简单打家结舍 LC198 中等打家劫舍2 LC213中等最长连续递增序列 LC674 简单乘积最大子数组LC152 中等最长递增子序列LC300 中等最长重复子数组LC718最长公共子串NC BM66最长公共子序列LC1143 中等完全平方数LC279零钱兑换 LC322 中等单…...

统计模型----决策树

决策树 &#xff08;1&#xff09;决策树是一种基本分类与回归方法。它的关键在于如何构建这样一棵树。决策树的建立过程中&#xff0c;使用基尼系数来评估节点的纯度和划分的效果。基尼系数是用来度量一个数据集的不确定性的指标&#xff0c;其数值越小表示数据集的纯度越高。…...

C# List 复制之深浅拷贝

C# List 复制 之深浅拷贝 声明类 public class TestStu{public int Number{get;set; }public string Name{get;set; }}public static async Task<int> Main(string[] args){var stu1 new TestStu(){Number 1,Name "1"};var stu2 new TestStu(){Numbe…...

论<script> 标签可以直接写在 HTML 文件中的哪些位置?(可以将 <script> 标签直接插入到 HTML 文件的任何位置)

可以将 <script> 标签直接插入到 HTML 文件的任何位置&#xff0c;以在相应位置执行 JavaScript 代码。 以下是几个示例&#xff1a; 1.<head> 元素内部&#xff1a;在 <head> 元素内部放置 <script> 标签时&#xff0c;脚本将在页面加载过程中被下载和…...

【MySQL进阶】--- 存储引擎的介绍

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【MySQL学习专栏】&#x1f388; 本专栏旨在分享学习MySQL的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 目录 一、什么…...

self-XSS漏洞SRC挖掘

本文由掌控安全学院 - 一朵花花酱 投稿 Markdown是一种轻量级标记语言&#xff0c;创始人为约翰格鲁伯&#xff08;John Gruber&#xff09;。它允许人们使用易读易写的纯文本格式编写文档&#xff0c;然后转换成有效的 XHTML&#xff08;或者HTML&#xff09;文档。这种语言吸…...

1859. 将句子排序

目录 一、题目 二、代码 一、题目 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 二、代码 定义了一个vector<vector<string>> v(MAX);采用const string& word : v[k] word 就会依次取得 v[k] 中的每个元素&#xff08;v[k][0],…...

普通学校,普通背景,普通公司,不普通总结。

作者&#xff1a;阿秀 InterviewGuide大厂面试真题网站&#xff1a;https://top.interviewguide.cn 这是阿秀的第「313」篇原创 小伙伴们大家好&#xff0c;我是阿秀。 可能很多人点开牛客、知乎、B站&#xff0c;一看帖子的标题都是"某985xxxx"、"不入流211xxx…...

Flink之Watermark生成策略

在Flink1.12以后,watermark默认是按固定频率周期性的产生. 在Flink1.12版本以前是有两种生成策略的: AssignerWithPeriodicWatermarks周期性生成watermarkAssignerWithPunctuatedWatermarks[已过时] 按照指定标记性事件生成watermark 新版本API内置的watermark策略 单调递增的…...

提升API文档编写效率,Dash for Mac是你的不二之选

在编写和开发API文档的过程中&#xff0c;你是否经常遇到查找困难、管理混乱、效率低下等问题&#xff1f;这些都是让人头疼的问题&#xff0c;但现在有了Dash for Mac&#xff0c;一切都将变得简单而高效。 Dash for Mac是一款专为API文档编写和管理设计的工具&#xff0c;它…...

无人注意,新安装的 Ubuntu 23.04 不支持安装 32 位应用

导读新安装的 Ubuntu 23.04 不支持安装 32 位应用。 无人注意&#xff0c;新安装的 Ubuntu 23.04 不支持安装 32 位应用 有用户报告&#xff0c;在新安装的 Ubuntu 23.04 上从 Ubuntu 仓库安装的 Steam 客户端是不工作的。在 Ubuntu 23.04 中使用了基于 Flutter 的新安装程序…...

全面横扫:dlib Python API在Linux和Windows的配置方案

前言 在计算机视觉和人工智能领域&#xff0c;dlib是一个备受推崇的工具库。它为开发者提供了强大的图像处理、机器学习和深度学习功能。在计算机视觉项目中&#xff0c;配置dlib Python API是一个重要的初始步骤。本文将引导读者详细了解在Linux和Windows系统上安装和配置dli…...

30种编程语言写国庆节快乐,收藏后改改留着拜年用

文章目录 核心代码版多行代码单行代码 核心代码版 Python&#xff1a;print(“国庆节快乐&#xff01;&#xff01;&#xff01;”)C&#xff1a;printf(“国庆节快乐&#xff01;&#xff01;&#xff01;”);C&#xff1a;cout<<“国庆节快乐&#xff01;&#xff01;…...

SpringBoot2.7.9 配置文件加载方式

ConfigDataLocationResolver接口方法说明 isResolvable: 判断是否是需要转换的资源 resolve: 将单个ConfigDataLocation转换为ConfigDataResource集合&#xff0c;在激活环境配置之前加载&#xff0c;也就是profile文件加载之前加载 resolveProfileSpecific: 将单个ConfigDataL…...

详解C语言—文件操作

目录 1. 为什么使用文件 2. 什么是文件 3. 文件的使用 文件指针 文件的打开和关闭 三个标准的输入/输出流&#xff1a; 4. 文件的顺序读写 对字符操作&#xff1a; fputc&#xff1a; fgetc&#xff1a; 练习复制整个文件&#xff1a; 对字符串操作&#xff1a;…...

IntelliJ IDEA 常用快捷键一览表

目录 1-IDEA的日常快捷键 第1组&#xff1a;通用型 第2组&#xff1a;提高编写速度&#xff08;上&#xff09; 第3组&#xff1a;提高编写速度&#xff08;下&#xff09; 第4组&#xff1a;类结构、查找和查看源码 第5组&#xff1a;查找、替换与关闭 第6组&#xff1a…...

做网站需要视频衔接怎么/长沙seo行者seo09

知识点&#xff1a; 1-可视块模式方法 2-替换方法 3-自定义快捷键方式 今天刚好重新在linux上手工搭建完Lamp环境&#xff0c;用来下vi操作&#xff0c;一段时间不用就有些生疏了&#xff0c;正好经常要注释&#xff0c;回顾下自己会的方法&#xff0c;小结一把。 使用系统&…...

程序开发语言/重庆seo网络优化师

多线程使得程序中的多个任务可以同时执行 在一个程序中允许同时运行多个任务。在许多程序设计语言中&#xff0c;多线程都是通过调用依赖系统的过程或函数来实现的 为什么需要多线程&#xff1f;多个线程如何在单处理器系统中同时运行&#xff1f; 多线程可以使您的程序更具响应…...

广州旅游网站建设设计公司/西安seo排名优化推广价格

一、机制 对象关系映射&#xff08;Object Relational Mapping&#xff0c;ORM&#xff09;&#xff0c;将对数据库的操作&#xff0c;映射为对类的操作&#xff0c;一个表对应一个类。sqlalchemy无法独立对数据库进行操作&#xff0c;需要借助其他第三方插件&#xff0c…...

可以做旅行计划的网站/百度客服中心人工在线咨询

作为一个软件工程团队&#xff0c;离不开下面三个要素&#xff1a;支持&#xff0c;即分享、责任和合作。 分享是出色技术团队的另一个关键要素&#xff0c;它是团队的基石之一。只有通过分享&#xff0c;团队才有可能实现11 > 2这种效应&#xff0c;分享也是让团队在整体上…...

做谷歌网站使用什么统计代码吗/沈阳seo优化新势力

在官网(https://www.scootersoftware.com/download.php) 下载Beyond Compare并安装成功后&#xff0c;可以免费试用30天。 然后可以使用下面的命令清除已经试用的时间&#xff0c;重新开始试用。 rm "/Users/$(whoami)/Library/Application Support/Beyond Compare/reg…...

台湾做的h游戏下载网站/百度推广区域代理

企业管理培训&#xff1a;如何提升中层管理者的执行力&#xff1f;企业中层管理都懂得一个道理“高效执行力是企业做大做强的核心武器&#xff0c;没有好的执行力&#xff0c;再好的决策&#xff0c;也只是一个良好的愿望”&#xff0c;如何提升企业中层管理者的执行力&#xf…...