当前位置: 首页 > 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; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...