Java【手撕双指针】LeetCode 18. “四数之和“, 图文详解思路分析 + 代码
文章目录
- 前言
- 一、四数之和
- 1, 题目
- 2, 思路分析
- 3, 代码
前言
各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你:
📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等
📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等
📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)
一、四数之和
1, 题目
OJ链接
这题是在"三数之和"的基础上进行了一些提升, 而"三数之和"又是在两数之和的基础上的提升, 核心算法思想是一致的, 不熟悉 “两数之和” 这道题的小伙伴建议看一下 这篇文章 , 不熟悉 “三数之和” 这道题的小伙伴建议看一下 这篇文章 , 弄懂了前两道题, 做出本题会非常轻松
2, 思路分析
最简单的暴力枚举 : 四层 for 循环, 从先固定一个数, 在剩余区间上固定一个数, 再在剩余区间上固定一个数, 暴力枚举依次找第四个数, 判断这四个数的和是否为 0 (目标值), 时间复杂度为O(N⁴), 必然会超出时间限制
- 先对数组排序(有序后使用对撞双指针可以大大提高效率)
- 使用 k 指针先固定一个数
- 在
剩余区间上
使用 “三数之和” 的解法找到另外三个数
固定住 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, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆…...
OpenCV处理图像和计算机视觉任务时常见的算法和功能
当涉及到OpenCV处理图像和计算机视觉任务时,有许多常见的具体算法和功能。以下是一些更具体的细分: 图像处理算法: 图像去噪:包括均值去噪、高斯去噪、中值滤波等,用于减少图像中的噪声。 直方图均衡化:用…...

Flutter实现StackView
1.让界面之间可以嵌套且执行动画。 2.界面的添加遵循先进后出原则。 3.需要使用AnimateView,请看我上一篇博客。 演示: 代码: Stack: import package:flutter/cupertino.dart;///栈,先进后出 class KqWidgetStack {final Lis…...
c++ future与promise
C11 标准中 头文件中包含了以下几个类和函数: Providers 类:std::promise, std::package_taskFutures 类:std::future, shared_future.Providers 函数:std::async()其他类型:std::future_error, std::future_errc, st…...
在x86机器上的Docker运行arm64容器
1. 引言 工作中常用电脑主机CPU为x86架构,有时由于产品需要,我们需要编译aarch64架构的SDK或者应用程序供使用或者测试。 一种比较快捷的方式是使用aarch64的CPU构建相应操作系统,实现真机运行。但在无arm架构CPU环境下,我们可否…...

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

uni-app里使用webscoket
实现思路和vue中是一样的。如果想看思路可以看这篇文章:websocket 直接上可以运行的代码: 一、后端nodeJS代码: 1、新建项目文件夹 2、初始化项目: npm init -y 3、项目里安装ws npm i ws --save 4、nodeJS代码࿱…...
jdk17+springboot使用webservice,踩坑记录
这几天wms对接lbpm系统,给我的接口是webservice的,老实说,这个技术很早,奈何人家只支持这个。 环境说明:JDK17 springboot2.6.6。网上很多教程是基于jdk8的,所以很多在17上面跑不起来。折腾两天,…...
计算机网络文件拆分—视频流加载、断点续传
视频流加载 视频流加载的原理是通过网络传输和播放器解码来实现的。 首先,视频文件会被分成一系列小的数据包,通常是以流的形式传输,这些数据包通过网络传输到用户设备。在传输过程中,可以采用各种协议,如HTTP、RTSP…...
JVM 给对象分配内存空间
指针碰撞空闲列表TLAB 为对象分配空间的任务实际上便等同于把一块确定大小的内存块从Java堆中划分出来。 指针碰撞:(Bump The Pointer) 堆的内存是绝对规整的,内存主要分为两部分,所有使用过的内存被放在一边&#x…...

Excel·VBA二维数组组合函数、组合求和
目录 1,二维数组组合函数举例 2,组合求和 之前的文章《ExcelVBA数组组合函数、组合求和》和《ExcelVBA数组排列函数》,都是针对一维数组的组合和排列 二维数组组合:对一个m行*n列的二维数组,每行抽取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的个数
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 1 的个数(也被称为汉明重量)。 提示: 请注意,在某些语言(如 Java)中…...

安防监控视频平台EasyCVR视频汇聚平台调用接口出现跨域现象的问题解决方案
视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等,能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...
Python中的一些常用操作
文章目录 一. Python操作之-- 使用Python 提取PDF文件中的表格数据!二:三: Python中的 staticmethodclassmethod方法四: 反斜杠 \五: 终端的解释器提示符号修改六: python使用json.dumps输出中文七…...
go语言调用python脚本
文章目录 代码gopython 在 go语言中调用 python 程序,你可能会用到 代码 亲测 go 测试 go 文件 func TestR(t *testing.T) {// 设置要执行的Python脚本和参数scriptPath : "../nansen.py"arg1 : "nansen"// 执行Python脚本cmd : exec.Comm…...

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

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

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

他们朝我扔泥巴(scratch)
前言 纯~~~属~~~虚~~~构~~~(同学看完短视频要我做,蟹蟹你) 用scratch做的,幼稚得嘞( ̄_ ̄|||)呵呵(强颜欢笑) 完成视频 视频试了好久,就是传不上来,私信我加我…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(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"> 关键配置点: 路径验证:确保相对路径.…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...

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

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

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

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...