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

【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. 四数之和

文章目录 题目方法一&#xff1a;双指针&#xff08;定2动2&#xff09; 题目 方法一&#xff1a;双指针&#xff08;定2动2&#xff09; 这题可以参考【LeetCode-中等题】15. 三数之和 区别在于&#xff0c;三数之和只需要用一个for循环定住一个数&#xff0c;然后设置两个前…...

每日一题 102二叉树的层序遍历

题目 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 示例 2&#xff1a…...

牛客: 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&#xff08;int&#xff09;12&#xff0c;二维数组名是一个指向每一行的指针&#xff0c;a:0061FF08, a1:0061FF14prin…...

nodejs格式化输入

需求 比如我现在要格式为Axxx-xxx&#xff08;xxx是数字&#xff09;的格式&#xff0c;但是输入有可能为A1-2这种情况&#xff0c;就需要补零&#xff0c;变成A001-002 代码实现 const regex /^A(\d)\-(\d)$/; // 正则匹配桩号合法格式const match input.match(regex);if…...

国家网络安全周 | 金融日,一起 get金融行业数据安全

2023国家网络安全宣传周 热度一直在持续&#xff01; 9月15日是国家网络安全宣传金融日。 目前随着国际形势愈发严峻&#xff0c;金融机构基础设施的全面数字化升级&#xff0c;带来了全新的安全问题。数据安全不单是技术问题&#xff0c;更是已经成为一个关系社会稳定发展的…...

分布式事务解决方案之TCC

分布式事务解决方案之TCC 什么是TCC事务 TCC是Try、Confirm、Cancel三个词语的缩写&#xff0c;TCC要求每个分支事务实现三个操作&#xff1a;预处理Try、确认 Confirm、撤销Cancel。Try操作做业务检查及资源预留&#xff0c;Confirm做业务确认操作&#xff0c;Cancel实现一个…...

Git 的基础命令 码云 gitee

就比如&#xff0c;我们的开发吧&#xff0c;我自己本地分支是dqh&#xff0c;远程分支也是new //我开始提交代码 //1&#xff0c;git add . //2&#xff0c;git commit -mXXX功能 //3&#xff0c;git pull origin new(你们现在这个版本的开发分支) //这里…...

探索工业4.0:数字孪生如何重塑工业生产流程?

在过去的几十年里&#xff0c;工业生产经历了从机械化、自动化到数字化的巨大转变。随着工业4.0的到来&#xff0c;我们正处于第四次工业革命的边缘&#xff0c;这次革命将由数字孪生技术引领。本文将深入探讨数字孪生在工业生产中的应用和潜力。 数字孪生&#xff08;Digital …...

window server事件ID说明

重启&#xff1a;1074 6013&#xff1a;系统运行时间 6008&#xff1a;非正常关机或者意外关机 WindowsServer2012R2事件id6008什么意思&#xff1f; 在Windows Server 2012 R2中&#xff0c;事件ID 6008是一个系统事件&#xff0c;它通常表示系统的非正常关机或意外关机。当系…...

router-link 和 router-view的区别

router-link 实现路由之间的跳转 router-view&#xff08;路由出口组件 -> 渲染路径匹配到的视图组件&#xff09; 当你访问的地址与路由path相符时&#xff0c;会将指定的组件替换该router-view router-link router-link 点击实现路由跳转&#xff0c;to属性指向目标地址&…...

【Leetcode】139.单词拆分

一、题目 1、题目描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例1: 输入: s = “leetcode”, wordDict = [“leet”, “cod…...

PMP考试一定要报培训班吗?

随着近年来PMP证书在国内日渐吃香&#xff0c;越来越多人开始报考PMP考试&#xff0c;甚至不少企业还会通过各项奖励政策来鼓励内部项目骨干去考取PMP证书。 免费送备考资料。 很多初次参加PMP考试的人会有这种疑惑&#xff0c;那就是考PMP证书必须要参加培训班吗? 在我看来&…...

dart 学习 之 Getters and setters

前言 任何需要对属性进行更多控制而不是允许简单字段访问的时候&#xff0c;你都可以自定义 getter 和 setter。 正文 讲解 Getter&#xff08;获取器&#xff09;和Setter&#xff08;设置器&#xff09;是面向对象编程中用于控制对类属性访问的特殊方法。Getter用于获取属…...

使用融云 CallPlus SDK,一小时实现一款 1V1 视频应用

9 月 21 日&#xff0c;融云直播课 社交泛娱乐出海最短变现路径如何快速实现一款 1V1 视频应用&#xff1f; 欢迎点击小程序报名~ 1V1 音视频、远程服务类应用的实现利器——融云 CallPlus SDK 上线&#xff01; 关注【融云全球互联网通信云】了解更多 作为新一代音视频通话场…...

Redis Part1

单体架构&#xff1a;一台Web服务器、一台数据库服务器。 1.了解NoSql 什么是Nosql&#xff1f; NoSQL&#xff0c;即Not-Only-SQL&#xff0c;意思就是我们干事情不能只用SQL&#xff0c;泛指非关系型的数据库&#xff01;NoSQL定位&#xff1a;作为关系型数据库的补充&am…...

代理HTTP使用不当会出现哪些问题?如何正确使用代理服务?

代理HTTP是一种常见的网络代理方式&#xff0c;它为客户端和服务器之间提供中间层&#xff0c;转发上下游的请求和响应。正确使用代理HTTP可以提高采集效率、增加网络安全性、加速网络速度、保护用户隐私。但是&#xff0c;使用不当就难以达到预期的效果&#xff0c;在使用代理…...

利用芯片74hc165为单片机增加输入扩展端口proteus仿真arduino

我们前面的博文《输入端口少如何扩展&#xff1f;74hc148或74ls148级联在arduino中实现16转4的应用》介绍了148,148输入后可以立即输出到数码管&#xff0c;可以说它是自带编BCD编码器的。而今天这里我们主要介绍的74hc165是没有编码器&#xff0c;这里我们以proteus为仿真环境…...

docker真实IP解决

背景 在微服务的环境中使用docker部署各个应用&#xff0c;部分应用使用容器内的真实ip暴露出服务。会导致微服务之间调用出现网络超时&#xff0c;要解决这个问题需要让微服务暴露为宿主机的ip 解决 方式一 使用docker-compose的配置 network_mode: "host" emq…...

Linux 内存泄漏检测的基本原理

一、mtrace分析内存泄露 mtrace&#xff08;memory trace&#xff09;&#xff0c;是 GNU Glibc 自带的内存问题检测工具&#xff0c;它可以用来协助定位内存泄露问题。 它的实现源码在glibc源码的malloc目录下&#xff0c;其基本设计原理为设计一个函数 void mtrace ()&…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

Axure零基础跟我学:展开与收回

亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...

npm安装electron下载太慢,导致报错

npm安装electron下载太慢&#xff0c;导致报错 背景 想学习electron框架做个桌面应用&#xff0c;卡在了安装依赖&#xff08;无语了&#xff09;。。。一开始以为node版本或者npm版本太低问题&#xff0c;调整版本后还是报错。偶尔执行install命令后&#xff0c;可以开始下载…...

数据挖掘是什么?数据挖掘技术有哪些?

目录 一、数据挖掘是什么 二、常见的数据挖掘技术 1. 关联规则挖掘 2. 分类算法 3. 聚类分析 4. 回归分析 三、数据挖掘的应用领域 1. 商业领域 2. 医疗领域 3. 金融领域 4. 其他领域 四、数据挖掘面临的挑战和未来趋势 1. 面临的挑战 2. 未来趋势 五、总结 数据…...