力扣刷题:四数相加Ⅱ
题目详情:

解法一:暴力枚举
对于这道题,我们的第一思路就是暴力枚举,我们可以写一个四层的for循环进行暴力匹配,只要相加的结果等于0就进行统计。但是我们会发现,我们的事件复杂度为O(N^4)事件复杂度非常大,所以如果使用这个思路进行问题的解决一定会超时,所以我们采用其他思路进行题目的解答操作。
解法二:暴力枚举内部优化
对于这道题目来说,我第一感觉就是对暴力枚举策略进行优化操作。进行思考,我们会发现最内层的循环我们可以将其使用二分查找的算法进行优化,让我们的时间复杂度变成O(N^3*logN),对于重复的数据,我们只需要从一点向四周进行展开即可。操作如下图所示:

但是我们在编写好代码之后会发现存在特殊情况,会使得我们的算法的时间复杂度恢复为O(N^4),特殊情况如下:


所以我们需要重新进行优化,我们可以提前对数组当中的数据进行处理,使用哈希表进行映射,哈希表的键为数组当中数据的值,哈希表的值为数组当中该值出现的次数。将上述代码实现结果如下:
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {long long count = 0;long long target = 0;int n = nums1.size();//对数组当中的元素进行处理map<int, int> nums1Num;map<int, int> nums2Num;map<int, int> nums3Num;map<int, int> nums4Num;vector<vector<int>> nums1VNum;vector<vector<int>> nums2VNum;vector<vector<int>> nums3VNum;vector<vector<int>> nums4VNum;for (int i = 0; i < n; i++){nums1Num[nums1[i]]++;nums2Num[nums2[i]]++;nums3Num[nums3[i]]++;nums4Num[nums4[i]]++;}//之后由于map不支持随机访问也就是无法使用二分查找进行优化,所以我们采用vector的二维数组进行代替map执行之后的操作,将数据转化进入vector当中for (auto e : nums1Num){nums1VNum.push_back({ e.first,e.second });}for (auto e : nums2Num){nums2VNum.push_back({ e.first,e.second });}for (auto e : nums3Num){nums3VNum.push_back({ e.first,e.second });}for (auto e : nums4Num){nums4VNum.push_back({ e.first,e.second });}for (int i = 0; i < nums1VNum.size(); i++){for (int j = 0; j < nums2VNum.size(); j++){for (int k = 0; k < nums3VNum.size(); k++){//之后对最后一个数组进行优化target = 0 - (long long)nums1VNum[i][0] - nums2VNum[j][0] - nums3VNum[k][0];//也就是需要在最后一个数组当中查找target数据int left = 0;int right = nums4VNum.size() - 1;while (left <= right){int mid = left + (right - left) / 2;if (nums4VNum[mid][0] == target){//从mid开始向左右进行查找符合条件的数据count = count + nums1VNum[i][1] * nums2VNum[j][1] * nums3VNum[k][1] * nums4VNum[mid][1];break;}else if (nums4VNum[mid][0] > target){right = mid - 1;}else{left = mid + 1;}}}}}return count;
} //存在一个可以进行优化的算法
};

但是我的的代码依旧不能通过测试,代码运行的时间依旧过长,所以我们需要重新整理思路进行问题的解决。
解法三:两两合并法
在官方题解当中我们可以学到一个解法:我们可以将四个数组分成为两个一组的形式,将一组当中的两个数组进行相加合并,将两个数组当中的元素进行完全匹配相加,合并之后就可以将两组新的数据进行匹配,之后就可以将题目的要求修改为两个数组查找指定的值。需要注意的是:我们同样需要使用哈希表进行数据的处理,以提高代码的运行速率。
我们会发现这种算法的时间复杂度为O(N^2),其主要需要进行的操作就是数组的合并,以及之后的数据查找操作。根据上述思路所编写的代码如下所示:
class Solution {
public:int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> ret;for (auto u: A) {for (auto v: B) {ret[u + v]++;}}int count = 0;for (auto u: C) {for (auto v: D) {if (ret.count(-u - v)) {count += ret[-u - v];}}}return count;}
};
时间复杂度分析:
相关文章:
力扣刷题:四数相加Ⅱ
题目详情: 解法一:暴力枚举 对于这道题,我们的第一思路就是暴力枚举,我们可以写一个四层的for循环进行暴力匹配,只要相加的结果等于0就进行统计。但是我们会发现,我们的事件复杂度为O(N^4)事件复杂度非常大…...
如果通过Glide 设置图片圆角
要给图片设置一个圆角,通常方法是在ImageView 标签外添加一个CardView 标签,然后设置圆角值,但是今天遇到一个问题就是 RecyclerView Item 中这样操作的话会遇到这样的一个报错: Cannot call this method while RecyclerView is computing a layout or scrolling androidx.rec…...
Chatgpt学习技巧
论文润色指令 论文润色常用指令 通用话术: Below is a paragraph from an academic paper. Polish the writing to meet the academic style, improve the spelling, grammar, clarity, concision and overall readability. When necessary, rewrite the whole se…...
[初学rust] 06_rust 元组
rust 元组 表现形式 和python的元组类似,rust中的元组是一个有序列表,可以包含多种不同类型的数据。 let tup (500, 6.4, a);模式匹配解构元组 和python中的解构一样,rust也支持模式匹配解构元组,但是需要注意的是࿰…...
基于 LlaMA 3 + LangGraph 在windows本地部署大模型 (四)
基于 LlaMA 3 LangGraph 在windows本地部署大模型 (四) 大家继续看 https://lilianweng.github.io/posts/2023-06-23-agent/的文档内容 第三部分:工具使用 工具的使用是人类的一个显着而显着的特征。我们创造、修改和利用外部物体来完成超…...
C++进阶:哈希(1)
目录 1. 简介unordered_set与unordered_map2. 哈希表(散列)2.1 哈希表的引入2.2 闭散列的除留余数法2.2.1 前置知识补充与描述2.2.2 闭散列哈希表实现 2.3 开散列的哈希桶2.3.1 结构描述2.3.2 开散列哈希桶实现2.3.3 哈希桶的迭代器与key值处理仿函数 3.…...
第三节课,功能2:开发后端用户的管理接口-- postman--debug测试
一、如何使用postman 网址: https://www.postman.com/downloads/ 【Postman小白教程】五分钟学会如何使用Postman~_哔哩哔哩_bilibili postman安装使用_bowser agent在postman哪里-CSDN博客 二、下载后 登录,开始测试 2.1 关于postman 报错&#…...
Docker-compsoe部署prysm-beacon-chain + geth服务(geth版本v1.14.0)
1、创建目录结构 ~ # mkdir -p /data/docker-compose/eth ~ # cd /data/docker-compose/eth /data/docker-compose/eth# mkdir beacondata eth ethdata prysm2、编写prysm-beacon-chain Dockerfile和启动脚本文件 /data/docker-compose/eth# vim Dockerfile /data/docker-…...
前端人员如何理解进程和线程
进程和线程的概念: 进程和线程本质都是cpu工作过程的时间片。 进程可以理解为cpu在运行指令即加载保存上下文所要用的时间。也可以理解为一个应用程序运行的实例。 线程是进程中更小的单位,描述一段指令所需要的时间。 进程是资源分配的最小单位…...
Linux下网络命令
目录 需求1-查看本机是否存在22端口解法1解法2解法3 需求2-查看其他主机是否存在22端口解法1解法2解法3 需求3-查看TCP连接解法1/2 需求4-统计80端口tcp连接次数解法 需求5-查看总体网络速度解法 需求6-查看进程流量解法 需求7-dns解法 需求8-traceroute到baidu解法 需求9-查看…...
Php swoole和mqtt
在 PHP 中使用 Swoole 处理 MQTT 订阅消息是一种高效的方式,可以充分利用 Swoole 协程的非阻塞特性和高性能 I/O 处理能力。下面是一个示例代码,演示了如何使用 Swoole 的 MQTT 客户端来订阅消息,并加以详细说明。 1. 安装 Swoole 首先&…...
Spring STOMP-连接到消息代理
STOMP 代理中继维护一个与消息代理的“系统”TCP 连接。这个连接仅用于来自服务器端应用程序的消息,不用于接收消息。您可以为此连接配置STOMP凭据(即STOMP帧的login和passcode头部)。这在XML命名空间和Java配置中都以systemLogin和systemPas…...
Excel中的`MMULT`函数
Excel中的MMULT函数是一个用于执行矩阵乘法运算的函数。矩阵乘法是线性代数中的一个基本运算,它允许我们计算两个矩阵的乘积,得到一个新的矩阵。与普通的标量乘法不同,矩阵乘法涉及到行与列的对应元素相乘然后求和的过程。MMULT函数在进行数据…...
孩子多大可以接触python?学习python的好处
孩子接触Python的年龄并没有明确的界限,一般来说,6岁以上的孩子可以开始学习Python编程。虽然Python是一门高级编程语言,但它的语法简单易懂,适合初学者入门。通过学习Python编程,孩子可以培养逻辑思维、创造力和解决问…...
四川汇昌联信:拼多多网点怎么开?大概需要多少钱?
想要开一家拼多多网点,你肯定很关心需要准备多少资金。下面,我们就来详细解答这个问题,并从多个角度分析开设网点的要点。 一、 开设拼多多网点,首要任务是确定启动资金。根据不同的经营模式和地区差异,成本会有所不同…...
ROS 2边学边练(43)-- 利用GTest写一个基本测试(C++)
前言 在ROS(Robot Operating System)中,gtest(Google Test)是一个广泛使用的C测试框架,用于编写和执行单元测试。这些测试可以验证ROS节点、服务和消息等的正确性和性能。 如果我们需要在写的包中添加测试&…...
3.整数运算
系列文章目录 信息的表示和处理 : Information Storage(信息存储)Integer Representation(整数表示)Integer Arithmetic(整数运算)Floating Point(浮点数) 文章目录 系列文章目录前…...
uri.getQueryParameters(name)返回一个列表(List)
uri.getQueryParameters(name)返回一个列表(List)而不是单个值的原因在于URI(统一资源标识符)中查询参数(query parameters)的设计允许同一个名称(name)对应多个值。这意味着一个查询…...
鸿蒙ArkUI开发:常用布局【主轴】
ArkUI中常用布局容器 线性布局(Row/Column) 线性布局的子元素在线性方向上(水平方向和垂直方向)依次排列线性布局容器包括[Row]和[Column]。Column容器内子元素按照垂直方向排列,Row容器内子元素按照水平方向排列开发…...
Spring Security 入门 2
1.项目实战 就以RuoYi-Vue 为例吧,主要以下几点原因: 基于 Spring Security 实现。 基于 RBAC 权限模型,并且支持动态的权限配置。 基于 Redis 服务,实现登录用户的信息缓存。 前后端分离。同时前端采用 Vue ,相对来…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...
