当前位置: 首页 > news >正文

LeetCode18.四数之和

题目链接:18. 四数之和 - 力扣(LeetCode)

这道题是在三数之和上改编出来的,在写这道题之前可以尝试以下三数之和(15. 三数之和 - 力扣(LeetCode));

1.常规解法(会超时)

由于这道题的结果不能出现含相同元素的三元组,则可以先对目标数组排,以防出现结果中元素相同但顺序不同的情况;

接下可以遍历这个数组,先找到所有的三元组,再挑选出符合条件的三元组,代码如下:

    public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();int n = nums.length;Arrays.sort(nums);for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {for (int l = k + 1; l < n; l++) {if ((long)nums[i] + (long)nums[j] + (long)nums[k] + (long)nums[l] == (long)target) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);list.add(nums[l]);if (!ret.contains(list)) {ret.add(list);}}}}}}return ret;}

注意:我们再进行判断时,涉及到四个数据相加,由于整形数据的最大值是2147483647,会出现1000000000 + 1000000000 + 1000000000  +1000000000 = -294967296的情况,这与实际情况不符,这时就需要类型转换,由于long类型的数据范围更大,就可以将int转化为long再相加比较。

2.双指针算法

和三数之和一样,我么可以先固定最后一个数,在前面的数中找到和为(target - 最后一个数);

因为有去重操作,可以先对数组从小到大排序;

先定义四个指针p1,p2,left,right,p1指向最后一个数,p2指向倒数第二个数,left指向第一个数,right指向p2前一个数;

现保持p1和p2不动,让left与right相向运动,若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] == target,则将这个四元组添加到结果中,由于不能出现出重复的四元组,就需要去除与left和right指向元素相同的元素;若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] < target,由单调性知,以left为基准,right左边的数均小于right指向的元素,相加之后结果必小于target,就需要将left向右移动一位;若(long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] > target,由单调性知,以right为基准,left右边的元素均大于left指向的元素,相加之后结果必大于target,就需要将right左移一位;

当left与right相遇后,内层的一轮循环就结束了,就需要将p2向左移动一位,同样的,也需要进行去重操作,除去与p2指向元素相同的元素;

当p2==1时,p2已经走完一遍,就需要向左移动p1继续下一轮循环,同样的,也需要进行去重操作,去除与p1指向元素相同的元素,流程图与代码如下:

    public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;int p1 = n - 1;while (p1 > 2) {int p2 = p1 - 1;while (p2 > 1) {int left = 0;int right = p2 - 1;while (left < right) {if ((long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] == target) {List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[p1]);list.add(nums[p2]);ret.add(list);int numLeft = nums[left++];while (nums[left] == numLeft && left < right) {left++;}int numRight = nums[right++];while (nums[right] == numRight && left < right) {right--;}} else if ((long)nums[left] + (long)nums[right] + (long)nums[p1] + (long)nums[p2] < target) {left++;} else {right--;}}int numP2 = nums[p2--];while (nums[p2] == numP2 && p2 > 1) {p2--;}}int numP1 = nums[p1--];while (nums[p1] == numP1 && p1 > 2) {p1--;}}return ret;}

希望读者指出不足之处! 

 

相关文章:

LeetCode18.四数之和

题目链接&#xff1a;18. 四数之和 - 力扣&#xff08;LeetCode&#xff09; 这道题是在三数之和上改编出来的&#xff0c;在写这道题之前可以尝试以下三数之和&#xff08;15. 三数之和 - 力扣&#xff08;LeetCode&#xff09;&#xff09;&#xff1b; 1.常规解法&#xf…...

jmeter出参保存到文件,保存失败解决

1、添加JSON提取 2、添加beanshell FileWriter writer new FileWriter("C:/Users/xxx/Desktop/signUrl.csv", true); writer.write(vars.get("company_name")"\t"vars.get("signUrl")"\n"); writer.close(); 写文件的两个…...

黑龙江网络安全等级保护办理机制

黑龙江的网络安全等级保护机制根据《网络安全法》和相关法规要求&#xff0c;信息系统按照安全等级从低到高分为五级&#xff0c;分别为一般、重要、非常重要、特别重要和特别敏感。不同等级的信息系统必须实施相应的安全措施&#xff0c;以确保系统免受内外部威胁&#xff0c;…...

小红的行列式构造

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题目描述 小红希望你构造一个3阶行列式&#xff0c;满足每个元素的绝对值不小于1&#xff0c;且行列式的值等于xxx。你能帮帮她吗&#xff1f; 输入描述: 一个整数xxx −100≤x≤100 输出描…...

pyflink过滤kafka数据

from pyflink.table import (TableEnvironment, EnvironmentSettings)# 输入、输出、过滤条件 columns_in [ ... ]columns_out [ ... ] filter_condition "name 蒋介石 and sex 男"# 创建执行环境t_env TableEnvironment.create(EnvironmentSettings.in_stream…...

Webpack 完整指南

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;Webpack篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来webpack篇专栏内容:webpack介绍 目录 介绍 一、webpack 1.1、webpack是什么 1.2 webpack五个核心配置 1.…...

如何在 Ubuntu20.04 安装FTP Server vsftpd

1.安装&#xff1a; sudo apt-get install vsftpd 2.启动 sudo service vsftpd start //启动 sudo service vsftpd stop //停止 sudo service vsftpd restart //重新启动 3.打开配置文件 sudo nano /etc/vsftpd.conf 4.配置&#xff1a;限制在指定目录&…...

基于FPGA的DDS信号发生器(图文并茂+深度原理解析)

篇幅有限,本文详细源文件已打包 至个人主页资源,需要自取...... 前言 DDS(直接数字合成)技术是先进的频率合成手段,在数字信号处理与硬件实现领域作用关键。它因低成本、低功耗、高分辨率以及快速转换时间等优点备受认可。 本文着重探究基于 FPGA 的简易 DDS 信号发生器设…...

QT:绘制事件和定时器

1.绘制时针 xx.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimer> #include<QPainter> #include <QTime>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpubl…...

【算法——递归回溯】

这个东西还是很重要的&#xff0c;直接决定了你的动态规划章节的学习深度 78. 子集 方法1&#xff1a; vector<vector<int>>V; void dfs(vector<int> v,vector<int> nums,int index) {if(indexnums.size()) V.push_back(v);else{v.push_back(nums[i…...

手机在网状态接口的使用和注意事项

手机在网状态接口是用于查询手机号码在运营商数据库中的实时状态的工具&#xff0c;这种接口在互联网金融、贷款、租赁、保险等相关行业中尤为重要&#xff0c;因为它可以帮助这些行业进行更有效的风控审核。以下是对手机在网状态接口的详细介绍&#xff1a; 一、手机在网状态…...

WebGl 使用uniform变量动态修改点的颜色

在WebGL中&#xff0c;uniform变量用于在顶点着色器和片元着色器之间传递全局状态信息&#xff0c;这些信息在渲染过程中不会随着顶点的变化而变化。uniform变量可以用来设置变换矩阵、光照参数、材料属性等。由于它们在整个渲染过程中共享&#xff0c;因此可以被所有使用该着色…...

Leetcode 划分字母区间

题目要求&#xff1a; 将字符串 s 划分成尽量多的片段&#xff0c;保证每个片段中出现的字母不会出现在其他片段中。 具体解释如下&#xff1a; 尽量多的片段&#xff1a;题目要求的是在划分过程中&#xff0c;我们要尽量让划分的片段数量最大化&#xff0c;而不是最少化。每…...

可编辑div遇到的那些事

在日常开发中有时可能会遇到input 或 textarea 不能满足的开发场景&#xff0c;比如多行输入的情况下&#xff0c;textarea 的右下角icon 无法去除, 所以此时可以使用div 设置可编辑状态&#xff0c;完成功能开发&#xff0c;在开发的过程中仍会遇到一下问题。 1&#xff0c;如…...

什麼是高速HTTP代理?

高速HTTP代理是一種用於加速和優化互聯網連接的技術。它通過在用戶和目標網站之間充當仲介伺服器&#xff0c;幫助用戶快速訪問網路資源。HTTP代理不僅可以提高訪問速度&#xff0c;還能提供一定程度的隱私保護和安全性。 高速HTTP代理的工作原理 HTTP代理伺服器位於用戶設備…...

三子棋(C 语言)

目录 一、游戏设计的整体思路二、各个步骤的代码实现1. 菜单及循环选择的实现2. 棋盘的初始化和显示3. 轮流下棋及结果判断实现4. 结果判断实现 三、所有代码四、总结 一、游戏设计的整体思路 &#xff08;1&#xff09;提供一个菜单让玩家选择人机对战、玩家对战或者退出游戏…...

HWS赛题 入门 MIPS Pwn-Mplogin(MIPS_shellcode)

解题所涉知识点&#xff1a; 泄露或修改内存数据&#xff1a; 堆地址&#xff1a;栈地址&#xff1a;栈上数据的连带输出(Stack Leak) && Stack溢出覆盖内存libc地址&#xff1a;BSS段地址&#xff1a; 劫持程序执行流程&#xff1a;[[MIPS_ROP]] 获得shell或flag&am…...

纯血鸿蒙启动公测,爱加密鸿蒙加固平台发布,助力鸿蒙应用安全运营!

鸿蒙系统打破了移动操作系统两极格局&#xff0c;实现操作系统核心技术的自主可控、安全可靠&#xff0c;在神州大地上掀起一波科技革新的浪潮&#xff0c;HarmonyOS NEXT成为大型企业必须要布局的应用系统之一。 HarmonyOS NEXT于10月8日正式开启公测&#xff0c;距离面向全体…...

MySQL中 truncate、drop和delete的区别

MySQL中 truncate、drop和delete区别 truncate 执行速度快&#xff0c;删除所有数据&#xff0c;但是保留表结构不记录日志事务不安全&#xff0c;不能回滚可重置自增主键计数器 drop 执行速度较快&#xff0c;删除整张表数据和结构不记录日志事务不安全&#xff0c;不能回…...

什么开放式耳机值得买?开放式耳机推荐排行榜!

长时间佩戴传统入耳式耳机有时可能会影响耳道健康&#xff0c;鉴于此&#xff0c;转而选择不入耳设计的开放式耳机就成了不少人的新倾向&#xff0c;它们有助于减少细菌滋生和耳道闷热的烦恼。为了帮助大家找到合适的选项&#xff0c;下面我将列举一些市面上口碑不错的开放式耳…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...