力扣刷题:四数相加Ⅱ

        题目详情:

        解法一:暴力枚举

    对于这道题,我们的第一思路就是暴力枚举,我们可以写一个四层的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;}
};

        时间复杂度分析:
        

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3014877.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

电度表抄表是什么?什么叫电度表抄表?

一、电度表抄表的概念和作用 电度表抄表是电力系统中一个基本但非常重要的阶段。它指的是对安装在用户处电度表开展载入&#xff0c;记录下来电力消耗的值&#xff0c;便于测算电费的一个过程。此项工作不仅有利于供电公司精确扣除电费&#xff0c;都是监控和管理电力工程应用…

【前端--Vue】组件之间的多种通信方式,一文彻底搞懂组件通信!

本篇将重点讲解vue中的多种组件通信方式&#xff0c;包括【父传子】【子传父】【兄弟组件通信】【依赖注入】等等&#xff0c;并提供具体案例来让小伙伴们加深理解、彻底掌握&#xff01;喜欢的小伙伴们点赞收藏&#xff0c;持续关注哦~&#x1f495; &#x1f49f; 上一篇文章…

浅谈智能电气火灾监控系统的设计及应用

摘要&#xff1a;致电气火灾的原因是多方面的&#xff0c;主要成因包括漏电、绝缘层老化、短路、电火花密集、接地发生故障、电气设备自然、接触不良和电流超负荷等。文章分析电气火灾的成因&#xff0c;并探索电气火灾监控系统的设计方案与注意事项。 关键词&#xff1a;电气…

推荐5个免费的国内平替版GPT

提起AI&#xff0c;大家第一个想到的就是GPT。 虽然它确实很厉害&#xff0c;但奈何于我们水土不服&#xff0c;使用门槛有些高。 不过随着GPT的爆火&#xff0c;现在AI智能工具已经遍布到各行各业了&#xff0c;随着时间的推移&#xff0c;国内的AI工具也已经“百花盛放”了…

多模态大模型学杂了能力反下降?新研究:MoE+通用专家解决冲突

微调&#xff0c;能让通用大模型更加适配具体的行业应用。 但现在&#xff0c;研究人员们却发现&#xff1a; 对多模态大模型做“多任务指令微调”&#xff0c;大模型可能会“学得多错得多”&#xff0c;因为不同任务之间的冲突&#xff0c;导致泛化能力下降。 △多模态指令微…

进制乘法表(任意进制均可以)

#include <iostream> // 包含输入输出流库 #include <vector> // 包含向量库&#xff0c;未使用&#xff0c;可以删除 #include <string> // 包含字符串库using namespace std; // 使用标准命名空间// 将十进制数转换为P进制形式的字符串 string toBase(…

uniapp 拉起微信授权登录App

登录 微信开放平台 创建移动应用&#xff1a; 然后下一步&#xff1a; 输入相关信息 然后在项目中配置&#xff1a; 通用链接页面需要在页面中配置拉起你的App的 UrlSchemes 具体可参考 uniapp 自定义App UrlSchemes-CSDN博客 示例代码&#xff1a; uni.login({"prov…

【MySQL】连接查询(JOIN 关键字)—— 图文详解:内连接、外连接、左连接、左外连接、右连接、右外连接

文章目录 连接查询驱动表连接查询分类 内连接&#xff08;INNER JOIN&#xff09;内连接 —— 等值连接内连接 —— 自然连接&#xff08;NATURAL JOIN&#xff09;内连接 —— 交叉连接&#xff08;笛卡尔积&#xff09; 外连接&#xff08;OUTER JOIN&#xff09;外连接 ——…

专注 APT 攻击与防御——红蓝对抗渗透测试

在团体渗透测试的项目中&#xff0c;如红蓝对抗&#xff0c;团队渗透测试比赛等&#xff0c;最重要的是过程与结果实时共享于团队&#xff0c;例如&#xff1a;A同学nmap目标站&#xff0c;B同学也nmap目标站&#xff0c;这在对抗比赛中是极其浪费时间也是非常容易引起防火墙&a…

IDEA无法下载远程仓库jar包问题

问题描述&#xff1a; idea无法下载远程仓库jar包&#xff0c;最奇怪的是idea有多个项目&#xff0c;有些项目可以下载&#xff0c;有些项目不行。报错如下&#xff1a; 一开始&#xff1a; unable to find valid certification path to requested target Try run Maven impo…

SQLI-labs-第十三关和第十四关

目录 第十三关 1、判断注入点 2、判断当前数据库 3、爆表名 4、爆字段名 5、爆值 第十四关 1、判断注入点 知识点&#xff1a;POST方式的单引号和括号闭合错误,报错注入 第十三关 思路&#xff1a; 1、判断注入点 使用Burpsuite抓包 首先加入一个单引号&#xff0c;…

小米手机短信删除了怎么恢复?这里教你快速解决!

手机已经成为我们生活中不可或缺的一部分&#xff0c;比如小米手机。我们通过手机进行通讯、娱乐、学习等各种活动&#xff0c;其中&#xff0c;短信是我们日常生活中的重要信息来源之一。然而&#xff0c;我们可能会不小心删除了一些重要的短信&#xff0c;这时候我们就会想知…

【JS】call和 apply函数的详解

JavaScript 中 call() 和 apply() 函数的详解 在JavaScript中&#xff0c;call()和apply()都是非常重要的方法&#xff0c;用于调用函数时指定函数体内的this的值&#xff0c;从而实现不同对象之间的方法共享。尽管它们的功能非常相似&#xff0c;但在实际使用中各有其优势和特…

【前端】实现表格简单操作

简言 表格合并基础篇 本篇是在上一章的基础上实现&#xff0c;实现了的功能有添加行、删除行、逆向选区、取消合并功能。 功能实现 添加行 添加行分为在上面添加和在下面追加行。 利用 insertAdjacentElement 方法实现&#xff0c;该方法可以实现从前插入元素和从后插入元…

两个开关控制一盏灯

1.PLC控制电路 1.1双联控制 开关控制灯最为普遍、简单的做法是用一个开关控制一盏灯&#xff0c;除此之外&#xff0c;在某个位置需要用两个开关控制一盏灯&#xff0c;这就是双联控制。 灯的双联控制&#xff0c;在传统上要用到2个单刀双联开关&#xff0c;其电气原理图如下图…

【CTS :testExtensionAvailability】

【CTS】android.hardware.camera2.cts.CameraExtensionCharacteristicsTest#testExtensionAvailability 报错&#xff1a; java.lang.AssertionError: Extensions system property : true does not match with the advertised extensions: false expected: but was: 通过对这…

暗区突围端游海外版预下载教程 暗区突围端游海外版怎么注册 下载

暗区突围端游海外版预下载教程 暗区突围端游海外版怎么注册 下载 想必最近暗区突围PC版本的上线对于热爱这款游戏的玩家们是一件喜事&#xff0c;这款游戏自从手游上线之初就在全世界范围内引起了不小的轰动&#xff0c;作为逃离塔科夫这款游戏的竞品&#xff0c;刚上线时自然…

嵌入式学习——C语言基础——day14

1. 共用体 1.1 定义 union 共用名 { 数据类型1 成员变量1; 数据类型2 成员变量2; 数据类型3 成员变量3; .. }; 1.2 共用体和结构体的区别 1. 结构体每个成员变量空间独立 2. 共用体每个成员变量空间共享 1.3 判断内存大小端 1. 内存大端…

doris 启动be报错

doris版本是1.2.4 java版本是&#xff1a;1.8 刚开始我以为是版本不兼容问题&#xff0c;后面发现思路错了&#xff0c;版本是兼容的&#xff0c;报以下错我的原因是操作系统没有达到安装要求 以下是博主在部署doris x64(avx2)版本中遇到的小bug 在大家使用doris的时候应该…

翻译《The Old New Thing》- Does Windows have a limit of 2000 threads per process?

Does Windows have a limit of 2000 threads per process? - The Old New Thing (microsoft.com)https://devblogs.microsoft.com/oldnewthing/20050729-14/?p34773 Raymond Chen 2005年07月29日 Windows 是否有一个每个进程2000线程的限制&#xff1f; 简要 文章解释了在 W…