力扣刷题:四数相加Ⅱ

        题目详情:

        解法一:暴力枚举

    对于这道题,我们的第一思路就是暴力枚举,我们可以写一个四层的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://www.rhkb.cn/news/320895.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Word】写论文,参考文献涉及的上标、尾注、脚注 怎么用

一、功能位置 二、脚注和尾注区别 1.首先脚注是一个汉语词汇&#xff0c;论文脚注就是附在论文页面的最底端&#xff0c;对某些内容加以说明&#xff0c;印在书页下端的注文。脚注和尾注是对文本的补充说明。 2.其次脚注一般位于页面的底部&#xff0c;可以作为文档某处内容的…

机器人系统ros2内部接口介绍

内部 ROS 接口是公共 C API &#xff0c;供创建客户端库或添加新的底层中间件的开发人员使用&#xff0c;但不适合典型 ROS 用户使用。 ROS客户端库提供大多数 ROS 用户熟悉的面向用户的API&#xff0c;并且可能采用多种编程语言。 内部API架构概述 内部接口主要有两个&#x…

tcping的安装,ping和tcping的区别

ping和tcping的区别 功能不同&#xff1a; Ping&#xff1a;Ping是一种基于ICMP协议的网络工具&#xff0c;用于测试主机之间的连通性。它发送ICMP回显请求&#xff08;Echo Request&#xff09;到目标主机&#xff0c;并等待目标主机返回ICMP回显应答&#xff08;Echo Reply…

架构师:搭建Spring Security、OAuth2和JWT 的安全认证框架

1、简述 Spring Security 是 Spring 生态系统中的一个强大的安全框架,用于实现身份验证和授权。结合 OAuth2 和 JWT 技术,可以构建一个安全可靠的认证体系,本文将介绍如何在 Spring Boot 中配置并使用这三种技术实现安全认证,并分析它们的优点。 2、Spring Security Spri…

Java 笔记 13:Java 数组内容,数组的声明、创建、初始化、赋值等,以及内存分析

一、前言 记录时间 [2024-05-03] 系列文章简摘&#xff1a; Java 笔记 01&#xff1a;Java 概述&#xff0c;MarkDown 常用语法整理 Java 笔记 02&#xff1a;Java 开发环境的搭建&#xff0c;IDEA / Notepad / JDK 安装及环境配置&#xff0c;编写第一个 Java 程序 Java 笔记 …

会声会影电影片头怎么做 会声会影电影质感调色技巧 会声会影视频制作教程 会声会影下载免费中文版

片头通常通过一系列的图像、音乐和文字等元素来引入电影的主题和氛围。通过视觉和音频的呈现方式&#xff0c;给观众留下深刻的第一印象&#xff0c;为电影的故事铺设基础。这篇文章来学习一下会声会影电影片头怎么做&#xff0c;会声会影电影质感调色技巧。 一、会声会影电影…

ASP.NET视频点播系统的设计与实现

摘 要 本文阐述了基于WEB的交互式视频点播系统的协议原理、软件结构和设计实现。本视频点播系统根据流媒体传输原理&#xff0c;在校园局域网的基础上模拟基于Web的视频点播系统&#xff0c;实现用户信息管理、视频文件的添加、删除、修改及在线播放和搜索功能。本系统是一个…

XMall-Front:基于Vue.js的XMall商城前台页面的开发实践

XMall-Front&#xff1a;基于Vue.js的XMall商城前台页面的开发实践 摘要 随着电子商务的蓬勃发展&#xff0c;用户体验逐渐成为决定电商平台成功与否的关键因素。作为XMall商城项目的一部分&#xff0c;XMall-Front是基于Vue.js的前端页面开发&#xff0c;其目标是为用户提供…

关于地盘的紧固连接技术——SunTorque智能扭矩系统

底盘作为汽车的重要组成部分&#xff0c;其材料的选择和连接技术也日益受到关注。尤其是随着新能源汽车的兴起&#xff0c;底盘轻量化已成为一种趋势。在这一背景下&#xff0c;底盘新材料与紧固连接技术的研究和应用显得尤为重要。今天SunTorque智能扭矩系统和大家一起了解地盘…

Go通过CRUD实现学生管理系统

虽然这个项目没有什么含金量&#xff0c;但是可以熟悉go的语法和go开发项目的一般流程 项目结构 项目实现了五个功能&#xff1a; &#xff08;1)增加一个学生 &#xff08;2&#xff09;删除一个学生 &#xff08;3&#xff09;修改一个学生的信息 &#xff08;4&#xf…

9.4k Star!MemGPT:伯克利大学最新开源、将LLM作为操作系统、无限上下文记忆、服务化部署自定义Agent

9.4k Star&#xff01;MemGPT&#xff1a;伯克利大学最新开源、将LLM作为操作系统、无限上下文记忆、服务化部署自定义Agent 原创 Aitrainee | 公众号&#xff1a;AI进修生&#xff1a;AI算法工程师 / Prompt工程师 / ROS机器人开发者 | 分享AI动态与算法应用资讯&#xff0c;提…

N7552A是德科技N7552A电子校准件

181/2461/8938产品概述&#xff1a; 更小巧轻便的 2 端口模块&#xff0c;支持 3.5 mm 或 N 型 50 Ω 连接器&#xff0c;能够将校准时间缩短一半 特点 频率范围&#xff1a;直流至 9 GHz 使用 N 型或 3.5 mm 连接器 更小巧轻便的 2 端口电子校准件&#xff08;ECal&#xff…

力扣刷题--数组--第一天

一、数组 数组特点&#xff1a; 连续内存空间存储得数据元素类型一致数组可以通过下标索引查找数据元素&#xff0c;可以删除、替换、添加元素等 1.1 二分查找 使用二分查找需满足得条件&#xff1a; 数组是有序的&#xff1b;数组中没有重复元素&#xff1b;查找的target…

[Docker]容器的网络类型以及云计算

目录 知识梗概 1、常用命令2 2、容器的网络类型 3、云计算 4、云计算服务的几种主要模式 知识梗概 1、常用命令2 上一篇已经学了一些常用的命令&#xff0c;这里补充两个&#xff1a; 导出镜像文件&#xff1a;[rootdocker ~]# docker save -o nginx.tar nginx:laster 导…

关于Oracle 23ai 你要知道的几件事情

1.版本生命周期 23ai发布后的Oracle版本生命周期图&#xff0c;可以看到23ai是长期支持版本可以到2032年。 引申 Oracle版本分为两类 Innovation Release--创新版本&#xff0c;一般提供至少两年技术支持 Long Term Release --长期支持版本&#xff0c;一般提供5年premier和…

护眼灯排名前十的品牌有哪些?护眼灯品牌排行前十名推荐

近视在儿童中愈发普遍&#xff0c;许多家长开始认识到&#xff0c;除了学业成绩之外&#xff0c;孩子的视力健康同样重要。毕竟&#xff0c;学业的落后可以逐渐弥补&#xff0c;而一旦孩子近视&#xff0c;眼镜便可能成为长期伴随。因此&#xff0c;专业的护眼台灯对于每个家庭…

MySQL 中的HASH详解

MySQL中的哈希索引&#xff08;Hash Index&#xff09;是一种特殊的数据库索引类型&#xff0c;它利用哈希表&#xff08;Hash Table&#xff09;的数据结构来存储索引项。哈希表通过哈希函数&#xff08;Hash Function&#xff09;将索引列的值转化为一个固定长度的哈希码&…

腾锐D2000-8 MXM VPX,全国产,可广泛应用于边缘计算网关、入侵检测、VPN、网络监控等等应用领域

腾锐D2000-8 MXM VPX 1. 概述 XMVPX-108 是一款基于飞腾 D2000/8 处理器的低功耗逻辑运算和图形处理 VPX 刀片&#xff0c; 板贴 32GB DDR4 内存&#xff0c;搭载飞腾 X100 套片&#xff0c;满足通用 IO 接口功能。GPU 采用 MXM 小型插卡形式&#xff0c; 搭配 8GB 显卡。提供…

SAP 定义冻结库存不参与MRP运算简介

在MRP中,有着各种类型的特殊库存,在运行MRP时,某些特殊库存将被考虑,某些特殊库存又不被考虑,在实际过程中某个物料的库存,存在冻结库存,质检库存,调拨的在途库存,业务部门并不希望一味的将库存地点排除到MRP计算之外。希望在跑MRP的时候只考虑非限制库存。 针对以上…

使用STM32的FLASH保存数据

使用STM32的FLASH保存数据 为了防止“掉电丢失数据”&#xff0c;我们最先想到的是EEPROM&#xff0c;但是若考虑到降低成本和PCB布线的空间&#xff0c;使用CPU内部的FLASH空间来保存数据&#xff0c;是最好的选择。尤其是在STM32芯片上&#xff0c;应用案例还是比较多的。 …