【LeetCode-中等题】18. 四数之和
文章目录
- 题目
- 方法一:双指针(定2动2)
题目

方法一:双指针(定2动2)
这题可以参考【LeetCode-中等题】15. 三数之和
区别在于,三数之和只需要用一个for循环定住一个数,然后设置两个前后指针来根据sum的值和目标值比较来滑动指针
那么这题也是同理的,我们需要做的事就是定住2个数,要用两个for循环定住两个数,然后设置两个前后指针来根据sum的值和目标值比较来滑动指针
里面的处理细节很多需要注意,提前处理一些不可能满足条件的情况,减少时间复杂度

class Solution {
//for定2 指针动2public List<List<Integer>> fourSum(int[] nums, int target) {int len = nums.length;if(nums == null||len < 4 ) return new ArrayList<>();List<List<Integer>> res = new ArrayList<>();List<Integer> zres = null;Arrays.sort(nums);for(int i = 0 ;i< len-3 ;i++){//本身就是排序的数组 若第一个数就大于等于target了那么再加上任何一个数都会大于target,所以直接break// if(nums[i]>target) break;//这个条件不能要(对比LeetCode 15. 三数之和) 如果target是负数,第一个数大于target 在往下加可能会越来越小也是可以=taget的//但是如果target为0或正数,那么第一个数大于target 往下加会越来越大//去重操作 如果nums[i]==nums[i-1] 会得到一份与nums[i-1]一样的结果集if(i>0&&nums[i]==nums[i-1]) continue;// 若以i开头的四个元素就已经大于target了 那就无需做任何操作了,没必要了,在往后面加再怎么也会大于targetif((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;// 若以i开头元素和数组末尾的三个元素就还小于target了 那就没必要做此次循环,毕竟i加上后面最大的三个数都比target小if((long)nums[i]+nums[len-1]+nums[len-2]+nums[len-3] < target) continue;for(int j = i+1 ;j< len-2 ;j++){//这里就和 LeetCode 15. 三数之和 一样的原理 唯一多了一个提前判断// 这里的三个if与上面同理 if(j>i+1&&nums[j]==nums[j-1]) continue;if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;if((long)nums[i]+nums[j]+nums[len-1]+nums[len-2] < target) continue;int left = j+1;int right = len-1;while(left < right){long sum =(long) nums[i]+nums[j]+nums[left]+nums[right];if(sum == target) {zres = new ArrayList<>();//满足要求的子结果集zres.add(nums[i]);zres.add(nums[j]);zres.add(nums[left]);zres.add(nums[right]);res.add(zres);//加入大结果集while(left < right &&nums[left]==nums[left+1]) left++;//两个指针的去重while(left < right &&nums[right]==nums[right-1]) right--;left++;//移动指针到不重复的新区域right--;}else if(sum >target) right--;//缩小数值else left++;//扩大数值}}}return res;}
}
相关文章:
【LeetCode-中等题】18. 四数之和
文章目录 题目方法一:双指针(定2动2) 题目 方法一:双指针(定2动2) 这题可以参考【LeetCode-中等题】15. 三数之和 区别在于,三数之和只需要用一个for循环定住一个数,然后设置两个前…...
每日一题 102二叉树的层序遍历
题目 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2:…...
牛客: BM4 合并两个排序的链表
牛客: BM4 合并两个排序的链表 文章目录 牛客: BM4 合并两个排序的链表题目描述题解思路题解代码 题目描述 题解思路 以链表一为主链表,遍历两条链表 若当前链表二的节点val小于当前链表一的下一个节点val,则将链表链表二的该节点连到链表一的节点的下一个,链表一的当前节点往…...
C语言基础知识点(六)二维数组指针和地址
#include <stdio.h>int main() {int a[2][3] {2, 4, 6,8, 10, 12};printf("a:%p, a1:%p\n", a, a 1); // 相差3*sizeof(int)12,二维数组名是一个指向每一行的指针,a:0061FF08, a1:0061FF14prin…...
nodejs格式化输入
需求 比如我现在要格式为Axxx-xxx(xxx是数字)的格式,但是输入有可能为A1-2这种情况,就需要补零,变成A001-002 代码实现 const regex /^A(\d)\-(\d)$/; // 正则匹配桩号合法格式const match input.match(regex);if…...
国家网络安全周 | 金融日,一起 get金融行业数据安全
2023国家网络安全宣传周 热度一直在持续! 9月15日是国家网络安全宣传金融日。 目前随着国际形势愈发严峻,金融机构基础设施的全面数字化升级,带来了全新的安全问题。数据安全不单是技术问题,更是已经成为一个关系社会稳定发展的…...
分布式事务解决方案之TCC
分布式事务解决方案之TCC 什么是TCC事务 TCC是Try、Confirm、Cancel三个词语的缩写,TCC要求每个分支事务实现三个操作:预处理Try、确认 Confirm、撤销Cancel。Try操作做业务检查及资源预留,Confirm做业务确认操作,Cancel实现一个…...
Git 的基础命令 码云 gitee
就比如,我们的开发吧,我自己本地分支是dqh,远程分支也是new //我开始提交代码 //1,git add . //2,git commit -mXXX功能 //3,git pull origin new(你们现在这个版本的开发分支) //这里…...
探索工业4.0:数字孪生如何重塑工业生产流程?
在过去的几十年里,工业生产经历了从机械化、自动化到数字化的巨大转变。随着工业4.0的到来,我们正处于第四次工业革命的边缘,这次革命将由数字孪生技术引领。本文将深入探讨数字孪生在工业生产中的应用和潜力。 数字孪生(Digital …...
window server事件ID说明
重启:1074 6013:系统运行时间 6008:非正常关机或者意外关机 WindowsServer2012R2事件id6008什么意思? 在Windows Server 2012 R2中,事件ID 6008是一个系统事件,它通常表示系统的非正常关机或意外关机。当系…...
router-link 和 router-view的区别
router-link 实现路由之间的跳转 router-view(路由出口组件 -> 渲染路径匹配到的视图组件) 当你访问的地址与路由path相符时,会将指定的组件替换该router-view router-link router-link 点击实现路由跳转,to属性指向目标地址&…...
【Leetcode】139.单词拆分
一、题目 1、题目描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例1: 输入: s = “leetcode”, wordDict = [“leet”, “cod…...
PMP考试一定要报培训班吗?
随着近年来PMP证书在国内日渐吃香,越来越多人开始报考PMP考试,甚至不少企业还会通过各项奖励政策来鼓励内部项目骨干去考取PMP证书。 免费送备考资料。 很多初次参加PMP考试的人会有这种疑惑,那就是考PMP证书必须要参加培训班吗? 在我看来&…...
dart 学习 之 Getters and setters
前言 任何需要对属性进行更多控制而不是允许简单字段访问的时候,你都可以自定义 getter 和 setter。 正文 讲解 Getter(获取器)和Setter(设置器)是面向对象编程中用于控制对类属性访问的特殊方法。Getter用于获取属…...
使用融云 CallPlus SDK,一小时实现一款 1V1 视频应用
9 月 21 日,融云直播课 社交泛娱乐出海最短变现路径如何快速实现一款 1V1 视频应用? 欢迎点击小程序报名~ 1V1 音视频、远程服务类应用的实现利器——融云 CallPlus SDK 上线! 关注【融云全球互联网通信云】了解更多 作为新一代音视频通话场…...
Redis Part1
单体架构:一台Web服务器、一台数据库服务器。 1.了解NoSql 什么是Nosql? NoSQL,即Not-Only-SQL,意思就是我们干事情不能只用SQL,泛指非关系型的数据库!NoSQL定位:作为关系型数据库的补充&am…...
代理HTTP使用不当会出现哪些问题?如何正确使用代理服务?
代理HTTP是一种常见的网络代理方式,它为客户端和服务器之间提供中间层,转发上下游的请求和响应。正确使用代理HTTP可以提高采集效率、增加网络安全性、加速网络速度、保护用户隐私。但是,使用不当就难以达到预期的效果,在使用代理…...
利用芯片74hc165为单片机增加输入扩展端口proteus仿真arduino
我们前面的博文《输入端口少如何扩展?74hc148或74ls148级联在arduino中实现16转4的应用》介绍了148,148输入后可以立即输出到数码管,可以说它是自带编BCD编码器的。而今天这里我们主要介绍的74hc165是没有编码器,这里我们以proteus为仿真环境…...
docker真实IP解决
背景 在微服务的环境中使用docker部署各个应用,部分应用使用容器内的真实ip暴露出服务。会导致微服务之间调用出现网络超时,要解决这个问题需要让微服务暴露为宿主机的ip 解决 方式一 使用docker-compose的配置 network_mode: "host" emq…...
Linux 内存泄漏检测的基本原理
一、mtrace分析内存泄露 mtrace(memory trace),是 GNU Glibc 自带的内存问题检测工具,它可以用来协助定位内存泄露问题。 它的实现源码在glibc源码的malloc目录下,其基本设计原理为设计一个函数 void mtrace ()&…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
