当前位置: 首页 > 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 ()&…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...