当前位置: 首页 > 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;私信我加我…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

AI,如何重构理解、匹配与决策?

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

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

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):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

基于SpringBoot在线拍卖系统的设计和实现

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

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

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