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

使用hashmap优化时间复杂度,leetcode1577

1577. 数的平方等于两数乘积的方法数

已解答

中等

相关标签

相关企业

提示

给你两个整数数组 nums1 和 nums2 ,请你返回根据以下规则形成的三元组的数目(类型 1 和类型 2 ):

  • 类型 1:三元组 (i, j, k) ,如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
  • 类型 2:三元组 (i, j, k) ,如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length

示例 1:

输入:nums1 = [7,4], nums2 = [5,2,8,9]
输出:1
解释:类型 1:(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)

示例 2:

输入:nums1 = [1,1], nums2 = [1,1,1]
输出:9
解释:所有三元组都符合题目要求,因为 1^2 = 1 * 1
类型 1:(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]
类型 2:(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]

示例 3:

输入:nums1 = [7,7,8,3], nums2 = [1,2,9,7]
输出:2
解释:有两个符合题目要求的三元组
类型 1:(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2:(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]

示例 4:

输入:nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
输出:0
解释:不存在符合题目要求的三元组

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 1 <= nums1[i], nums2[i] <= 10^5

 

 解决思路:直观来看,直接暴力遍历算法也是正确的,然而时间复杂度比较高O(n^3),根据leetcode的规律,只有数据规模小于100的时候,才能使用这个复杂度的算法。所以,需要优化,这里使用哈希表记录每个数组的平方值,然后统计第二个数组中nums1[j] * nums1[k] 是否==第一个数组中的平方值,有的话就相加,没有就继续。复杂度可以降低为O(n^2),通过测试。

class Solution {
public:int numTriplets(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();unordered_map<long, int> square_count1;unordered_map<long, int> square_count2;int count = 0;// 计算 nums1 和 nums2 每个元素的平方,并存储在哈希表中for (int num : nums1) {long square = (long)num * num;square_count1[square]++;}for (int num : nums2) {long square = (long)num * num;square_count2[square]++;}// 枚举 nums1 的所有可能的两个元素的乘积for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {long product = (long)nums1[i] * nums1[j];// 检查 product 的平方是否在哈希表中count+=square_count2[product];}}// 枚举 nums2 的所有可能的两个元素的乘积for (int i = 0; i < m; ++i) {for (int j = i + 1; j < m; ++j) {long product = (long)nums2[i] * nums2[j];// // 检查 product 的平方是否在哈希表中count+=square_count1[product];}}return count;}
};

执行用时分布

135ms

击败34.58%使用 C++ 的用户

消耗内存分布

37.60MB

击败9.34%使用 C++ 的用户

官方题解给了更快的算法。随着AI的大模型普及,以后程序员可能会成为历史,可能以后编程就是提示和应用工程师。但是算法的思想和解决问题的能力,这个暂时是AI无法替代的。

相关文章:

使用hashmap优化时间复杂度,leetcode1577

1577. 数的平方等于两数乘积的方法数 已解答 中等 相关标签 相关企业 提示 给你两个整数数组 nums1 和 nums2 &#xff0c;请你返回根据以下规则形成的三元组的数目&#xff08;类型 1 和类型 2 &#xff09;&#xff1a; 类型 1&#xff1a;三元组 (i, j, k) &#xff…...

3、设计模式之工厂模式1

工厂模式是什么&#xff1f;     工厂模式是一种创建者模式&#xff0c;用于封装和管理对象的创建&#xff0c;屏蔽了大量的创建细节&#xff0c;根据抽象程度不同&#xff0c;主要分为简单工厂模式、工厂方法模式以及抽象工厂模式。 简单工厂模式 看一个具体的需求 看一个…...

一个Promise全新API

1. 资讯速览 最近&#xff0c;Promise 新出了一个方法&#xff0c;已经进入 Stage 3 &#xff08;候选阶段&#xff09; &#xff0c;相信很快就能达到 Stage 4 &#xff08;完成阶段&#xff09;&#xff0c;并在项目中广泛使用。 这个方法就是 Promise.withResolvers。它是…...

【力扣hot100】刷题笔记Day25

前言 这几天搞工作处理数据真是类似我也&#xff0c;还被老板打电话push压力有点大的&#xff0c;还好搞的差不多了&#xff0c;明天再汇报&#xff0c;赶紧偷闲再刷几道题&#xff08;可恶&#xff0c;被打破连更记录了&#xff09;这几天刷的是动态规划&#xff0c;由于很成…...

webpack5零基础入门-4使用webpack处理less文件

1.安装less npm install less -D 2.创建less文件 .box{width: 100px;height: 100px;background: red; } 3.引入less文件并打包 执行npx webpack 报错无法识别less文件 4.安装less-loader并配置 npm install less-loader9 -D 这里指定一下版本不然会因为node版本过低报错 …...

Python机器学习预测+回归全家桶,新增TCN,BiTCN,TCN-GRU,BiTCN-BiGRU等组合模型预测...

截止到本期&#xff0c;一共发了4篇关于机器学习预测全家桶Python代码的文章。参考往期文章如下&#xff1a; 1.机器学习预测全家桶-Python&#xff0c;一次性搞定多/单特征输入&#xff0c;多/单步预测&#xff01;最强模板&#xff01; 2.机器学习预测全家桶-Python&#xff…...

一文了解Cornerstone3D中窗宽窗位的3种设置场景及原理

&#x1f506; 引言 在使用Cornerstone3D渲染影像时&#xff0c;有一个常用功能“设置窗宽窗位&#xff08;windowWidth&windowLevel&#xff09;”&#xff0c;通过精确调整窗宽窗位&#xff0c;医生能够更清晰地区分各种组织&#xff0c;如区别软组织、骨骼、脑组织等。…...

部署 LVS(nginx)+keepalived高可用负载均衡集群

目录 一、集群的概述 1、什么是集群 2、普通集群与负载均衡集群 2.1 普通集群&#xff08;Regular Cluster&#xff09; 2.2 负载均衡集群&#xff08;Load Balancing Cluster&#xff09; 2.3 高可用集群&#xff08;High Availability Cluster&#xff09; 2.4 区别 …...

Qt/QML编程之路:fork、vfork、exec、clone的对比及使用(46)

前言: 系统调用system call是OS提供的服务提供接口。系统调用fork()、vfork()、exec()和clone()都用于创建和操作进程。Linux下Qt编程也会用到vfork进行多进程间通信。让我们看一下以下每个系统调用的概述和比较: fork()、vfork()和clone()的工作原理相似,但在处…...

Go语言框架路由Controller控制器设计思路gin路由根据控制器目录分层生成路由地址

Controller设计好处 框架设计用controller分请求路由层级&#xff0c;应用从app目录开始对应请求url路由地址&#xff0c;这样设计师方便开发时候通过请求地址层级快速定位接口方法对应的代码位置。 例如api接口请求路径为&#xff1a;​​http://localhost:8110/​​busines…...

突破编程_C++_设计模式(责任链模式)

1 责任链模式的概念 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为设计模式&#xff0c;它允许对象以链式的方式组织起来&#xff0c;以便对请求进行处理。这种模式为多个对象处理同一请求提供了一个灵活的机制&#xff0c;而无需在发送者和多…...

php开发100问?

什么是 PHP&#xff1f;PHP 是一种什么类型的语言&#xff1f;PHP 的优缺点是什么&#xff1f;如何在服务器上配置 PHP&#xff1f;PHP 中的变量是如何声明和使用的&#xff1f;如何在 PHP 中输出文本和变量&#xff1f;什么是 PHP 的数据类型&#xff1f;如何在 PHP 中实现条件…...

flink实战--Flink任务资源自动化优化

背景 在生产环境Flink任务资源是用户在实时平台端进行配置,用户本身对于实时任务具体配置多少资源经验较少,所以存在用户资源配置较多,但实际使用不到的情形。比如一个 Flink 任务实际上 4 个并发能够满足业务处理需求,结果用户配置了 16 个并发,这种情况会导致实时计算资…...

tsv文件在大数据技术栈里的应用场景

是的&#xff0c;\t 是指制表符&#xff08;tab&#xff09;&#xff0c;它通常用作字段分隔符在 TSV&#xff08;Tab-Separated Values&#xff09;格式的文件中。TSV是一种简单的文本格式&#xff0c;它使用制表符来分隔每一列中的值&#xff0c;而每一行则代表一个数据记录。…...

vscode设置setting.json

{ // vscode默认启用了根据文件类型自动设置tabsize的选项 "editor.detectIndentation": false, // 重新设定tabsize "editor.tabSize": 2, // #每次保存的时候自动格式化 // "editor.formatOnSave": true, // #每次保存的时候将代码按eslint格式…...

Docker的安装及镜像加速的配置

文章目录 一.切换到root二.卸载旧版docker三.配置docker的yum库四.安装Docker五.Docker的启动和验证六.配置Docker阿里云镜像加速(全程免费) 该文章文章演示在Linux系统中安装docker&#xff0c;Windows安装docker请参考以下文章 Windows系统中安装docker及镜像加速的配置 一…...

AIGC时代IT人的迷茫有解(1):从“商业画布”到“个人画布”

IT人的迷茫和心态调整 最近打开新闻&#xff0c;各种IT老大都在说“AIGC时代&#xff0c;只要会说话&#xff0c;人人都会具备程序员的能力”,身边也有很多程序员朋友也已经在用GPT类的产品编程了。随着AIGC的发展&#xff0c;除了程序员&#xff0c;可能很多职业都会被替代或…...

Qt/QML编程之路:openglwidget和倒车影像的切换(43)

关于如何实现一个基于OpenGL的3d 图形,这个有很多专门的介绍,我在开发中遇到了这么一个问题: 如何实现一个倒车影像的video显示与一个3D物体显示的切换,因为开窗在同样的一个位置,如果车子倒车启动,则需要将原本显示3D的地方切换为视频图像的显示。 class testOpenGl : …...

Spring 初学者遇到的问题

TagLibraryValidator Spring 实战 5.2 中有个表单需要在 jsp 中遍历数组&#xff0c;添加&#xff1a;<% taglib uri"http://java.sun.com/jsp/jstl/core" prefix"c" %>&#xff0c;访问时发现有些问题&#xff1a; java.lang.NoClassDefFoundError…...

前端解决跨域问题( 6种方法 )

本专栏是汇集了一些HTML常常被遗忘的知识&#xff0c;这里算是温故而知新&#xff0c;往往这些零碎的知识点&#xff0c;在你开发中能起到炸惊效果。我们每个人都没有过目不忘&#xff0c;过久不忘的本事&#xff0c;就让这一点点知识慢慢渗透你的脑海。 本专栏的风格是力求简洁…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...