当前位置: 首页 > 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;下面我将列举一些市面上口碑不错的开放式耳…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...