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

双指针解决n数之和问题

1. 两数之和

1. 两数之和

  • 将时间复杂度降到O(n);
class Solution {// 双指针public int[] twoSum(int[] nums, int target) {int n=nums.length;int l=0;while(l<n){int r=n-1;// 找到第一个可能nums[l]+nums[r]==target的位置while(r>l){if(nums[l]+nums[r]==target){return new int[]{l,r};}r--;}l++;}return new int[0];}
}
class Solution {// 哈希表 public int[] twoSum(int[] nums, int target) {int n=nums.length;HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<n;i++){map.put(nums[i],i);}for(int i=0;i<n;i++){int another=target-nums[i];if(map.containsKey(another)&&map.get(another)!=i){return new int[]{i,map.get(another)};}}return new int[0];}
}

2. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

  • 将时间复杂度降到O(n);
class Solution {// 双指针public int[] twoSum(int[] numbers, int target) {int n=numbers.length;int l=0;while(l<n){int r=n-1;// 找到第一个可能nums[l]+nums[r]==target的位置while(r>l){if(numbers[l]+numbers[r]==target){return new int[]{l+1,r+1};}r--;}l++;}return new int[0];}
}
class Solution {// 双指针public int[] twoSum(int[] numbers, int target) {int l=0,r=numbers.length-1;while(l<r){if(numbers[l]+numbers[r]>target){r--;}else if(numbers[l]+numbers[r]<target){l++;}else{return new int[]{l+1,r+1};}}return new int[0];}
}

3. 三数之和

15. 三数之和
剑指 Offer II 007. 数组中和为 0 的三个数

  • 将时间复杂度降到O(n2);
class Solution {// 排序+双指针// a+b+c=0  ---> a=-(b+c)public List<List<Integer>> threeSum(int[] nums) {// 排序保证重复元素连续Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;int a=0;  // 确定第一个数while(a<n){// 分别确定第二、三个数int c=n-1;int b=a+1;while(b<n){while(c>b&&(-nums[a]<nums[b]+nums[c])){c--;}if(c==b){break;}if(-nums[a]==nums[b]+nums[c]){  // a+b+c=0  可行解List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);ans.add(cur);}// 找到下一个与b不重复的元素int d=b+1;while(d<n&&nums[d]==nums[b]){d++;}b=d;}// 找到下一个与a不重复的元素int e=a+1;while(e<n&&nums[e]==nums[a]){e++;}a=e;}return ans;}
}
class Solution {// 排序+双指针// a+b+c=0  ---> a=-(b+c)public List<List<Integer>> threeSum(int[] nums) {// 排序保证重复元素连续Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;int a=0;  // 确定第一个数while(a<n){// 找到下一个与a不重复的元素if(a==0||nums[a]!=nums[a-1]){// 确定第二个数int b=a+1;int c=n-1;while(b<n){// 找到下一个与b不重复的元素if(b==a+1||nums[b]!=nums[b-1]){// 确定第三个数while(c>b&&(nums[a]+nums[b]>-nums[c])){c--;}if(c==b){break;}if(nums[a]+nums[b]==-nums[c]){  // a+b+c=0  可行解List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);ans.add(cur);}}b++;}}a++;}return ans;}
}

4. 四数之和

18. 四数之和

  • 将时间复杂度降到O(n3);
class Solution {// 排序+双指针public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> ans=new ArrayList<>();int n=nums.length;// 第一个数int a=0;while(a<n){if(a==0||(nums[a]!=nums[a-1])){// 第二个数int b=a+1;while(b<n){if(b==a+1||(nums[b]!=nums[b-1])){// 第三个数int c=b+1;// 第四个数int d=n-1;while(c<n){if(c==b+1||(nums[c]!=nums[c-1])){long sum=nums[a]+nums[b]+nums[c]-target;// 第四个数while(d>c&&((long)nums[a]+nums[b]+nums[c]+nums[d]>target)){d--;}if(d==c){break;}// 可行解if((long)nums[a]+nums[b]+nums[c]+nums[d]==target){List<Integer> cur=new ArrayList<>();cur.add(nums[a]);cur.add(nums[b]);cur.add(nums[c]);cur.add(nums[d]);ans.add(cur);}}c++;}}b++;}}a++;}return ans;}
}

相关文章:

双指针解决n数之和问题

1. 两数之和 1. 两数之和 将时间复杂度降到O(n)&#xff1b; class Solution {// 双指针public int[] twoSum(int[] nums, int target) {int nnums.length;int l0;while(l<n){int rn-1;// 找到第一个可能nums[l]nums[r]target的位置while(r>l){if(nums[l]nums[r]targe…...

安全学习DAY07_其他协议抓包技术

协议抓包技术-全局-APP&小程序&PC应用 抓包工具-Wireshark&科来分析&封包 TCPDump&#xff1a; 是可以将网络中传送的数据包完全截获下来提供分析。它支持针对网络层、协议、主机、网络或端口的过滤&#xff0c;并提供and、or、not等逻辑语句来帮助你去掉无用…...

electron的electron-packager打包运行和electron-builder生产安装包过程,学透 Electron 自定义 Dock 图标

electron的electron-packager打包运行和electron-builder生产安装包过程 开发electron客户端程序&#xff0c;打包是绕不开的问题。 macOS 应用构建&#xff0c;看似近在咫尺&#xff0c;实则坑坑致命。 场景&#xff1a;mac笔记本打包&#xff0c;以及生产出可交付的软件安装…...

【无标题】深圳卫视专访行云创新马洪喜:拥抱AI与云原生,深耕云智一体化创新

人工智能&#xff08;AI&#xff09;是引领新一轮科技革命和产业变革的重要驱动力。因此&#xff0c;深圳出台相关行动方案&#xff0c;统筹设立规模1,000亿元的人工智能基金群&#xff0c;引导产业集聚培育企业梯队&#xff0c;积极打造国家新一代人工智能创新发展试验区和国家…...

jenkins通过流水线进行构建jar包

前言 最近项目上需要进行CICD,本篇博客主要分享各种骚操作 目录 前言操作如下:构建触发器测试哈哈操作如下: 1.下载Jenkins.war包上传到服务器上面,然后在同级目录下面创建如下脚本: #!/bin/bash# Jenkins安装目录 JENKINS_HOME=/usr/local/jenkins# Jenkins日志文件 LO…...

Android开发:通过Tesseract第三方库实现OCR

一、引言 什么是OCR&#xff1f;OCR(Optical Character Recognition&#xff0c;光学字符识别)是指电子设备(例如扫描仪或数码相机)检查纸上打印的字符&#xff0c;通过检测暗、亮的模式确定其形状&#xff0c;然后用字符识别方法将形状翻译成计算机文字的过程。简单地说&#…...

合并两个有序链表——力扣21

题目描述 法一 递归 class Solution { public:ListNode* mergeTwoLists(ListNode *l1, ListNode*l2){if(l1 nullptr){return l2;} else if (l2nullptr){return l1;} else if (l1->val<l2->val){l1->next mergeTwoLists(l1->next, l2);return l1;} else {l2-&g…...

企业数据,大语言模型和矢量数据库

随着ChatGPT的推出&#xff0c;通用人工智能的时代缓缓拉开序幕。我们第一次看到市场在追求人工智能开发者&#xff0c;而不是以往的开发者寻找市场。每一个企业都有大量的数据&#xff0c;私有的用户数据&#xff0c;自己积累的行业数据&#xff0c;产品数据&#xff0c;生产线…...

LabVIEW使用支持向量机对脑磁共振成像进行图像分类

LabVIEW使用支持向量机对脑磁共振成像进行图像分类 医学成像是用于创建人体解剖学图像以进行临床研究、诊断和治疗的技术和过程。它现在是医疗技术发展最快的领域之一。通常用于获得医学图像的方式是X射线&#xff0c;计算机断层扫描&#xff08;CT&#xff09;&#xff0c;磁…...

kafka面试题

kafka基本概念 Producer 生产者&#xff1a;负责将消息发送到 BrokerConsumer 消费者&#xff1a;从 Broker 接收消息Consumer Group 消费者组&#xff1a;由多个 Consumer 组成。消费者组内每个消费者负责消费不同分区的数据&#xff0c;一个分区只能由一个组内消费者消费&am…...

树的遍历(一题直接理解中序、后序、层序遍历,以及树的存储)

题目如下&#xff1a; 一个二叉树&#xff0c;树中每个节点的权值互不相同。 现在给出它的后序遍历和中序遍历&#xff0c;请你输出它的层序遍历。 输入格式 第一行包含整数 N&#xff0c;表示二叉树的节点数。 第二行包含 N 个整数&#xff0c;表示二叉树的后序遍历。 第…...

JVM系统优化实践(22):GC生产环境案例(五)

您好&#xff0c;这里是「码农镖局」CSDN博客&#xff0c;欢迎您来&#xff0c;欢迎您再来&#xff5e; 除了Tomcat、Jetty&#xff0c;另一个常见的可能出现OOM的地方就是微服务架构下的一次RPC调用过程中。笔者曾经经历过的一次OOM就是基于Thrift框架封装出来的一个RPC框架导…...

DevOps系列文章 之GitLabCI模板库的流水线

目录结构&#xff0c;jobs目录用于存放作业模板。templates目录用于存放流水线模板。这次使用​​default-pipeline.yml​​作为所有作业的基础模板。 作业模板 作业分为Build、test、codeanalysis、artifactory、deploy部分&#xff0c;在每个作业中配置了rules功能开关&…...

spring扩展点ApplicationContextAware解释

ApplicationContextAware是Spring框架中的一个扩展接口&#xff0c;用于获取和操作应用程序上下文&#xff08;ApplicationContext&#xff09;。通过实现ApplicationContextAware接口&#xff0c;可以在Bean中获取对应用程序上下文的引用&#xff0c;并进行进一步的操作。 具…...

力扣热门100题之最大子数组和【中等】【动态规划】

题目描述 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 示例 1&#xff1a; 输入&#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] 输出&a…...

导出为PDF加封面且分页处理dom元素分割

文章目录 正常展示页面导出后效果代码 正常展示页面 导出后效果 代码 组件内 <template><div><div><div class"content" id"content" style"padding: 0px 20px"><div class"item"><divstyle"…...

【C++入门】浅谈类、对象和 this 指针

文章目录 一、前言二、类1. 基本概念2. 类的封装3. 使用习惯成员函数定义习惯成员变量命名习惯 三、对象1. 基本概念2. 类对象的存储规则 四、this 指针1. 基本概念2. 注意事项3. 经典习题4. 常见面试题 一、前言 在 C 语言中&#xff0c;我们用结构体来描述一个事物的多种属性…...

【Linux命令200例】indent对C语言代码进行缩进和格式化

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;本文已收录于专栏&#xff1a;Linux命令大全。 &#x1f3c6;本专栏我们会通过具体的系统的命令讲解加上鲜活的实操案例对各个命令进行深入…...

Hive 调优集锦(1)

一、前言 1.1 概念 Hive 依赖于 HDFS 存储数据&#xff0c;Hive 将 HQL 转换成 MapReduce 执行&#xff0c;所以说 Hive 是基于Hadoop 的一个数据仓库工具&#xff0c;实质就是一款基于 HDFS 的 MapReduce 计算框架&#xff0c;对存储在HDFS 中的数据进行分析和管理。 1.2 架…...

【C++详解】——智能指针

目录 为什么需要智能指针 抛异常引发内存泄漏 内存泄漏 什么是内存泄漏&#xff0c;内存泄漏的危害 内存泄漏分类 检测内存泄漏常用工具 如何避免内存泄漏 智能指针的使用及原理 RAII 智能指针的原理 各类智能指针介绍 auto_ptr unique_ptr shared_ptr weak_ptr …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...