【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 ()&…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
