学习记录:js算法(十六):四数之和

2024-08-28 08:04

本文主要是介绍学习记录:js算法(十六):四数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 四数之和
      • 我的思路
    • 总结

四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  1. 0 <= a, b, c, d < n
  2. a、b、c 和 d 互不相同
  3. nums[a] + nums[b] + nums[c] + nums[d] == target
  4. 可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

我的思路
昨天写了三数之和,今天写四数,那肯定要使用不熟练的指针写法了。
网上思路
如上

我的思路

var fourSum = function (nums, target) {nums.sort((a, b) => a - b);const res = new Set();const n = nums.length;for (let i = 0; i < n - 3; i++) {for (let j = i + 1; j < n - 2; j++) {let left = j + 1;let right = n - 1;while (left < right) {const sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum === target) {res.add(`${nums[i]},${nums[j]},${nums[left]},${nums[right]}`);left++;right--;} else if (sum < target) {left++;} else {right--;}}while (j + 1 < n && nums[j] === nums[j + 1]) {j++;}}while (i + 1 < n && nums[i] === nums[i + 1]) {i++;}}return Array.from(res).map(quad => quad.split(',').map(Number));
}

讲解

  1. 对输入的数组 nums 进行 排序和去重 。是为了后续的双指针操作以及避免重复四元组的出现。
  2. 外层循环 i 从 0 到 n - 3,目的是 固定第一个数 nums[i]内层循环 j 从 i + 1 到 n - 2,目的是 固定第二个数 nums[j]。这样,就有了两个固定的数,接下来要寻找四个数中剩下的两个数。
  3. 定义两个指针 leftright,分别指向 当前固定数 j 之后的第一个元素数组的最后一个元素。然后通过 while (left < right) 循环 来寻找满足条件的四元组。
  4. 在循环中,需要计算当前四个数的和 sum
    • 如果 sum 等于目标值 target,则将这个四元组添加到 Set 中,并移动 leftright 指针,寻找其他可能的组合。
    • 如果 sum 小于目标值,说明我们需要更大的数,因此移动 left 指针向右。
    • 如果 sum 大于目标值,说明需要更小的数,因此移动 right 指针向左。
  5. 在每次内层循环结束后,需要跳过重复的元素,以确保不会得到重复的四元组。这个逻辑适用于 外层循环的 i 和内层循环的 j
  6. Set 中的字符串转换为数组形式。使用 Array.from(res)Set 转换为数组,然后用 map 方法将每个字符串分割成数字数组。

总结

今天特地用双指针的写法来解题的,说实话,我想了老半天,才在别人的代码下写出来的。。。

这篇关于学习记录:js算法(十六):四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114194

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

在Spring Boot中浅尝内存泄漏的实战记录

《在SpringBoot中浅尝内存泄漏的实战记录》本文给大家分享在SpringBoot中浅尝内存泄漏的实战记录,结合实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录使用静态集合持有对象引用,阻止GC回收关键点:可执行代码:验证:1,运行程序(启动时添加JVM参数限制堆大小):2,访问 htt

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,