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

如何妙用哈希表来优化遍历查找过程?刷题感悟总结,c++实现

先上题目
在这里插入图片描述
在这里插入图片描述
题目链接:题目链接

  • 这题我最先想到的就是前缀和a,构造好了以后就遍历每一个[l,r]数组(满足题目要求的连续区间数组),奈何倒数第二个样例时间超限
    在这里插入图片描述
  • 先给出原思路代码
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//vector<int> a;int x = 0;int len = nums.size();a.resize(len + 2, 0);a[1] = nums[0];for (int i = 2; i <= len; i++) {a[i] = nums[i - 1]; // 0号赋值,a[i] += a[i - 1];}// 核心需要优化的地方for (int i = 0; i <= len; i++) {for (int j = i + 1; j <= len; j++) {if (a[j] - a[i] == k)x++;}}return x;}
};
  • 但是介于给出的数组中可能有正数、负数,所以同样的前缀和大小可能有好几个,可以巧妙利用哈希表的find功能(或者count功能,都是查找函数),实现O(n)一次遍历全部数字就好了
  • 代码如下,已ac,主要是把上面那份代码的“核心需要优化的部分”修改
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//vector<int> a;int x = 0;int len = nums.size();a.resize(len + 2, 0);a[1] = nums[0];//从a[1]开始存前缀和for (int i = 2; i <= len; i++) {a[i] = nums[i - 1]; // 0号赋值,a[i] += a[i - 1];}unordered_map<int,int> myMap;// 核心需要优化的地方for (int i = 0; i <= len; i++) {//目的是a[i]-a[l]==k 所以要寻找a[l]if(myMap.count(a[i]-k)) x+=myMap[a[i]-k];myMap[a[i]]++;}return x;}
};
  • 这个思路让我想起之前做过一道题,几乎完全一样的思路,利用哈希表
    在这里插入图片描述
    在这里插入图片描述
    题目链接
    实现代码:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> myMap;vector<int> x;for(int i=0;i<nums.size();i++){//说明first是具体数值auto  it=myMap.find(target-nums[i]);if(it!=myMap.end()){x ={i,it->second};return x;}myMap[nums[i]]=i;}return  x;}
};
  • 共同点是它们都利用了哈希表(unordered_map)的特性来快速查找和存储信息,以便在遍历数组时可以高效地找到满足条件的元素或子数组。
  • 两道题都是对vector& nums, int k进行查找与操作,大家可以根据这两道题找找思路,以后碰到类似题考虑该方法~

相关文章:

如何妙用哈希表来优化遍历查找过程?刷题感悟总结,c++实现

先上题目 题目链接&#xff1a;题目链接 这题我最先想到的就是前缀和a&#xff0c;构造好了以后就遍历每一个[l,r]数组&#xff08;满足题目要求的连续区间数组&#xff09;&#xff0c;奈何倒数第二个样例时间超限 先给出原思路代码 class Solution { public:int subarray…...

【设计模式】漫谈设计模式

这篇文章里说一下对设计模式的个人的理解。本篇文章更类似于随笔而非技术文档。 设计模式最早是在上个世纪就被人提出来了&#xff0c;如今被奉为圣经&#xff0c;也就是GOF等人写的《设计模式》&#xff0c;其中的设计模式&#xff0c;是指导开发者如何进行开发出高内聚、低耦…...

第N5周:Pytorch文本分类入门

本文为365天深度学习训练营 中的学习记录博客原作者&#xff1a;K同学啊 任务&#xff1a; ●1. 了解文本分类的基本流程 ●2. 学习常用数据清洗方法 ●3. 学习如何使用jieba实现英文分词 ●4. 学习如何构建文本向量 一、前期准备 环境安装 这是一个使用PyTorch实现的简单文…...

SpringBoot 自定义 starter

1. 官方文档 SpringBoot 版本 2.6.13&#xff0c;相关链接 Developing with Spring Boot 1.1 什么是 Starter Starters are a set of convenient dependency descriptors that you can include in your application. You get a one-stop shop for all the Spring and relate…...

TDengine Invalid data format 问题定位

Invalid data format 看语义是数据类型不符&#xff0c;通常这个报错出现在使用行协议写入时。 如果是批量数据写入&#xff0c;想定位是哪条语句的问题&#xff0c;需要查看客户端日志。 如何确定使用的是哪个日志 lsof -p pidof taosadapter | grep taoslog如果没有安装lso…...

Spring Boot 使用 MongoDB 教程

&#x1f341; 作者&#xff1a;知识浅谈&#xff0c;CSDN签约讲师&#xff0c;CSDN博客专家&#xff0c;华为云云享专家&#xff0c;阿里云专家博主 &#x1f4cc; 擅长领域&#xff1a;全栈工程师、爬虫、ACM算法 &#x1f525; 微信&#xff1a;zsqtcyw 联系我领取学习资料 …...

Python办公自动化:使用openpyxl 创建与保存 Excel 工作簿

1 创建新的工作簿 在开始任何 Excel 操作之前&#xff0c;首先需要创建一个工作簿。openpyxl 提供了简单的接口来创建新的工作簿。 创建一个空白的工作簿 我们可以使用 openpyxl.Workbook() 来创建一个新的空白工作簿。以下是一个简单的示例&#xff1a; import openpyxl# …...

【张】#11 Union 共用体

Union 共用体可以存储不同的数据类型&#xff0c;但只能同时存储其中的一种类型。 #include <iostream> using namespace std;struct Product {char productName[20];int type;//1 int ,else charunion{int id_int;char id_chars[20];}; };int main(){Product product; …...

Xcode 在原生集成flutter项目

笔者公司有一个从2017年就开始开发的iOS和安卓原生项目&#xff0c;现在计划从外到内开始进行项目迁徙。 1》从gitee拉取flutter端的代码&#xff1b;&#xff08;Android报错Exception: Podfile missing&#xff09; 2》替换Xcode里的cocopods里Podfile的路径 然后报警 然后…...

ES6的promise

Promise是什么 1、Promise是js中的一个原生对象&#xff0c;是一种异步编程的解决方案。可以替换掉传统的回调函数解决方案&#xff0c;将异步操作以同步的流程表达出来。 2、Promise有三种状态&#xff1a;pending(初始化)、fulfilled(成功)、rejected(失败) 可以通过resolve(…...

轻松找回:如何在PostgreSQL 16中重置忘记的数据库密码

目录 1. 引言2. PostgreSQL 16的新特性简介3. 解决方法概述4. 方法一&#xff1a;通过修改pg_hba.conf文件重置密码5. 方法二&#xff1a;通过命令行进入单用户模式6. 方法三&#xff1a;使用pgAdmin工具重置密码7. 总结与最佳实践写在以后 1. 引言 你有没有过这样的经历&…...

EVAL长度突破限制

目录 突破15位限制 代码 绕过方式 第一种&#xff08;使用echo执行&#xff09; 第二种&#xff08;使用file_get_content追加文件后进行问件包含&#xff09; 第三种&#xff08;使用usort可变长参数&#xff09; 突破7位限制 第一种&#xff08;可以使用>创建文件…...

如何判断树上一个点是否在直径上

# 旅游规划 ## 题目描述 W市的交通规划出现了重大问题&#xff0c;市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。但由于人员不足&#xff0c;W市市长决定只在最需要安排人员的路口安排人员。 具体来说&#xff0c;W市的交通网络十分简单&#xff0c;由n个…...

docker 部署 RabbitMQ

命令 docker run -d --namerabbitmq \ -p 5671:5671 -p 5672:5672 -p 4369:4369 \ -p 15671:15671 -p 15672:15672 -p 25672:25672 \ -e RABBITMQ_DEFAULT_USERusername\ -e RABBITMQ_DEFAULT_PASSpassword\ -v /usr/local/rabbitmq/data:/var/lib/rabbitmq \ -v /usr/local/r…...

设计模式 - 过滤器模式

💝💝💝首先,欢迎各位来到我的博客!本文深入理解设计模式原理、应用技巧、强调实战操作,提供代码示例和解决方案,适合有一定编程基础并希望提升设计能力的开发者,帮助读者快速掌握并灵活运用设计模式。 💝💝💝如有需要请大家订阅我的专栏【设计模式】哟!我会定…...

使用 Locust 进行本地压力测试

在应用开发和运维过程中&#xff0c;了解应用在高负载情况下的表现至关重要。压力测试可以帮助你识别性能瓶颈和潜在问题。本文将介绍如何使用 Locust 工具进行本地压力测试&#xff0c;模拟高并发场景&#xff0c;并分析测试结果。 1. 什么是 Locust&#xff1f; Locust 是一…...

【图形学】TA之路-矩阵应用平移-旋转-大小

矩阵应用&#xff1a;在 Unity 中&#xff0c;Transform 和矩阵之间的关系非常密切。Transform 组件主要用于描述和控制一个物体在三维空间中的位置、旋转和缩放&#xff0c;而这些操作背后实际上都是通过矩阵来实现的 1. Transform 组件与矩阵的关系 Transform 组件包含以下…...

Spring 循环依赖解决方案

文章目录 1. 循环依赖的产生2. 循环依赖的解决模型3. 基于setter/Autowired 的循环依赖1_编写测试代码2_初始化 Cat3_初始化 Person4_ 回到 Cat 的创建流程5_小结 4. 基于构造方法的循环依赖5. 基于原型 Bean 的循环依赖6. 引人AOP的额外设计7. 总结 IOC 容器初始化bean对象的逻…...

可视化大屏:如何get到领导心目中的“科技感”?

你如果问领导可视化大屏需要什么风格的&#xff0c;领导大概率说科技感的&#xff0c;然后你就去做了&#xff0c;结果被劈了一顿&#xff0c;什么原因&#xff1f;因为你没有get到领导心目中描述的科技感。 一、为什么都喜欢科技感 科技感在可视化大屏设计中具有以下好处&am…...

基于Python的金融数据采集与分析的设计与实现

基于Python的金融数据采集与分析的设计与实现 “Design and Implementation of Financial Data Collection and Analysis based on Python” 完整下载链接:基于Python的金融数据采集与分析的设计与实现 文章目录 基于Python的金融数据采集与分析的设计与实现摘要第一章 绪论1…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...