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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...