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做的,幼稚得嘞( ̄_ ̄|||)呵呵(强颜欢笑) 完成视频 视频试了好久,就是传不上来,私信我加我…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...