学习记录: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

相关文章

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

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

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx