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

Java【手撕双指针】LeetCode 18. “四数之和“, 图文详解思路分析 + 代码

文章目录

  • 前言
  • 一、四数之和
    • 1, 题目
    • 2, 思路分析
    • 3, 代码


前言

各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你:
📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)

一、四数之和

1, 题目

OJ链接

这题是在"三数之和"的基础上进行了一些提升, 而"三数之和"又是在两数之和的基础上的提升, 核心算法思想是一致的, 不熟悉 “两数之和” 这道题的小伙伴建议看一下 这篇文章 , 不熟悉 “三数之和” 这道题的小伙伴建议看一下 这篇文章 , 弄懂了前两道题, 做出本题会非常轻松


2, 思路分析

最简单的暴力枚举 : 四层 for 循环, 从先固定一个数, 在剩余区间上固定一个数, 再在剩余区间上固定一个数, 暴力枚举依次找第四个数, 判断这四个数的和是否为 0 (目标值), 时间复杂度为O(N⁴), 必然会超出时间限制

  1. 先对数组排序(有序后使用对撞双指针可以大大提高效率)
  2. 使用 k 指针先固定一个数
  3. 剩余区间上使用 “三数之和” 的解法找到另外三个数
    在这里插入图片描述

固定住 k 时, 三数之和的总和定义为 threeTarget = target - nums[k],
固定住 i 时, 两数之和的总和定义为 twoTarget = threeTarget - nums[i]
总之就是, 四数之和中基本可以复用三数之和的代码, 而三数之和中又复用了两数之和的代码

三数之和中, 需要对 i, left, right 去重, 本题多了一个对 k 的去重, 去重方式和 i 的去重方式一致

在这里插入图片描述

当 k 指向 0 下标, i 指向 1 下标时, left 和 right 指针已经在剩余区间上遍历完了所有四元组, 接下来 k 不要着急自增, 因为 i 还没有遍历完(三数之和还没有执行完), 应该让 i 自增, left 回到 i + 1 位置开始, 继续执行未完成的"三数之和"

后续流程就不再赘述了, 就是把三数之和的代码放在 k 的循环之中, 稍作修改即可


3, 代码

	public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int k = 0;// k 的循环while(k < nums.length - 3){long threeTarget = target - nums[k];int i = k + 1;// i 在剩余区间上执行"三数之和"while(i < nums.length - 2) {long twoTarget = threeTarget - nums[i];int left = i + 1;int right = nums.length - 1;// left 和 right 在剩余区间上执行"两数之和"(对撞双指针)while(left < right) {List<Integer> inList = new ArrayList<>();if(nums[left] + nums[right] > twoTarget) {right--;}else if(nums[left] + nums[right] < twoTarget) {left++;}else {// left 和 right 的去重while(left < right && nums[right] == nums[right - 1]) {right--;}while(left < right && nums[left] == nums[left + 1]){left++;}inList.add(nums[k]);inList.add(nums[i]);inList.add(nums[left]);inList.add(nums[right]);list.add(inList);left++;right--;}}// i 的去重i++;while(nums[i] == nums[i - 1] && i < nums.length - 2) {i++;}}// k 的去重k++;while(nums[k] == nums[k - 1] && k < nums.length - 3) {k++;}}return list;}

相关文章:

Java【手撕双指针】LeetCode 18. “四数之和“, 图文详解思路分析 + 代码

文章目录 前言一、四数之和1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: &#x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 &#x1f4d7; Java数据结构: 顺序表, 链表, 堆…...

OpenCV处理图像和计算机视觉任务时常见的算法和功能

当涉及到OpenCV处理图像和计算机视觉任务时&#xff0c;有许多常见的具体算法和功能。以下是一些更具体的细分&#xff1a; 图像处理算法&#xff1a; 图像去噪&#xff1a;包括均值去噪、高斯去噪、中值滤波等&#xff0c;用于减少图像中的噪声。 直方图均衡化&#xff1a;用…...

Flutter实现StackView

1.让界面之间可以嵌套且执行动画。 2.界面的添加遵循先进后出原则。 3.需要使用AnimateView&#xff0c;请看我上一篇博客。 演示&#xff1a; 代码&#xff1a; Stack: import package:flutter/cupertino.dart;///栈&#xff0c;先进后出 class KqWidgetStack {final Lis…...

c++ future与promise

C11 标准中 头文件中包含了以下几个类和函数&#xff1a; Providers 类&#xff1a;std::promise, std::package_taskFutures 类&#xff1a;std::future, shared_future.Providers 函数&#xff1a;std::async()其他类型&#xff1a;std::future_error, std::future_errc, st…...

在x86机器上的Docker运行arm64容器

1. 引言 工作中常用电脑主机CPU为x86架构&#xff0c;有时由于产品需要&#xff0c;我们需要编译aarch64架构的SDK或者应用程序供使用或者测试。 一种比较快捷的方式是使用aarch64的CPU构建相应操作系统&#xff0c;实现真机运行。但在无arm架构CPU环境下&#xff0c;我们可否…...

centos7删除乱码文件

centos7删除乱码文件1. 小白教程&#xff0c;一看就会&#xff0c;一做就成。 1.解释 当文件名为乱码的时候&#xff0c;无法通过键盘输入文件名&#xff0c;所以在终端下就不能直接利用rm&#xff0c;mv等命令管理文件了。 但是每个文件都有一个i节点号&#xff0c;可以通过…...

uni-app里使用webscoket

实现思路和vue中是一样的。如果想看思路可以看这篇文章&#xff1a;websocket 直接上可以运行的代码&#xff1a; 一、后端nodeJS代码&#xff1a; 1、新建项目文件夹 2、初始化项目&#xff1a; npm init -y 3、项目里安装ws npm i ws --save 4、nodeJS代码&#xff1…...

jdk17+springboot使用webservice,踩坑记录

这几天wms对接lbpm系统&#xff0c;给我的接口是webservice的&#xff0c;老实说&#xff0c;这个技术很早&#xff0c;奈何人家只支持这个。 环境说明&#xff1a;JDK17 springboot2.6.6。网上很多教程是基于jdk8的&#xff0c;所以很多在17上面跑不起来。折腾两天&#xff0c…...

计算机网络文件拆分—视频流加载、断点续传

视频流加载 视频流加载的原理是通过网络传输和播放器解码来实现的。 首先&#xff0c;视频文件会被分成一系列小的数据包&#xff0c;通常是以流的形式传输&#xff0c;这些数据包通过网络传输到用户设备。在传输过程中&#xff0c;可以采用各种协议&#xff0c;如HTTP、RTSP…...

JVM 给对象分配内存空间

指针碰撞空闲列表TLAB 为对象分配空间的任务实际上便等同于把一块确定大小的内存块从Java堆中划分出来。 指针碰撞&#xff1a;&#xff08;Bump The Pointer&#xff09; 堆的内存是绝对规整的&#xff0c;内存主要分为两部分&#xff0c;所有使用过的内存被放在一边&#x…...

Excel·VBA二维数组组合函数、组合求和

目录 1&#xff0c;二维数组组合函数举例 2&#xff0c;组合求和 之前的文章《ExcelVBA数组组合函数、组合求和》和《ExcelVBA数组排列函数》&#xff0c;都是针对一维数组的组合和排列 二维数组组合&#xff1a;对一个m行*n列的二维数组&#xff0c;每行抽取1个元素进行组合&a…...

调用自实现MyGetProcAddress获得CreateFileA函数并调用创建写入文件

写文件如下 #include <iostream> #include <Windows.h>typedef HANDLE(WINAPI* CreateFileAFunc)(LPCSTR, DWORD, DWORD, LPSECURITY_ATTRIBUTES, DWORD, DWORD, HANDLE);DWORD MyGetProcAddress(_In_ HMODULE hModule,_In_ LPCSTR lpProcName ){PIMAGE_DOS_HEADE…...

Leetcode 191.位1的个数

编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为汉明重量&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&#xff09;中…...

安防监控视频平台EasyCVR视频汇聚平台调用接口出现跨域现象的问题解决方案

视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...

Python中的一些常用操作

文章目录 一. Python操作之-- 使用Python 提取PDF文件中的表格数据&#xff01;二&#xff1a;三&#xff1a; Python中的 staticmethodclassmethod方法四&#xff1a; 反斜杠 \五&#xff1a; 终端的解释器提示符号修改六&#xff1a; python使用json.dumps输出中文七&#xf…...

go语言调用python脚本

文章目录 代码gopython 在 go语言中调用 python 程序&#xff0c;你可能会用到 代码 亲测 go 测试 go 文件 func TestR(t *testing.T) {// 设置要执行的Python脚本和参数scriptPath : "../nansen.py"arg1 : "nansen"// 执行Python脚本cmd : exec.Comm…...

2.3 【MySQL】命令行和配置文件中启动选项的区别

在命令行上指定的绝大部分启动选项都可以放到配置文件中&#xff0c;但是有一些选项是专门为命令行设计的&#xff0c;比方说defaults-extra-file 、 defaults-file 这样的选项本身就是为了指定配置文件路径的&#xff0c;再放在配置文件中使用就没啥意义了。 如果同一个启动选…...

外部库/lib/maven依赖项 三者关系

外部库(存放项目初始配置的jar包)(它的文件夹里并没有包含lib文件夹的引的外部的依赖的jar包) lib(存放外部导入到项目的依赖的jar包) maven依赖项(管理项目所有的jar包依赖) 三者存放jar包的关系 项目所依赖的全部的jar包 maven依赖项的jar包 外部库中的jar包 lib中的…...

在线制作作息时间表

时光荏苒&#xff0c;岁月如梭&#xff0c;人们描述时光易逝的句子&#xff0c;多如星河。 一寸光阴一寸金&#xff0c;寸金难买寸光阴。 人生就是一段时间而已&#xff0c;所以我明白了一个道理 人生之中最大的浪费就是时间的浪费 因此我想我们教给我们孩子重要的一课应该也是…...

他们朝我扔泥巴(scratch)

前言 纯~~~属~~~虚~~~构~~~&#xff08;同学看完短视频要我做&#xff0c;蟹蟹你&#xff09; 用scratch做的&#xff0c;幼稚得嘞(&#xffe3;_&#xffe3;|||)呵呵&#xff08;强颜欢笑&#xff09; 完成视频 视频试了好久&#xff0c;就是传不上来&#xff0c;私信我加我…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...