如何妙用哈希表来优化遍历查找过程?刷题感悟总结,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进行查找与操作,大家可以根据这两道题找找思路,以后碰到类似题考虑该方法~

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

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

相关文章

【深入理解SpringCloud微服务】Ribbon源码解析

【深入理解SpringCloud微服务】Ribbon源码解析 Ribbon的原理RestTemplate中的拦截器链Ribbon的拦截器如何将拦截器放入到RestTemplate中 Ribbon中的核心类LoadBalancerAutoConfigurationLoadBalancerInterceptorLoadBalancerClientILoadBalancerServerListIRuleIPing Ribbon核心…

【高性能高易用】物联网AI开发套件----Qualcomm® RB3 Gen 2 开发套件

Qualcomm RB3 Gen 2 开发套件 专为高性能计算、高易用性而设计的物联网开发套件 Qualcomm RB3 Gen 2 开发套件拥有先进的功能和强大的性能&#xff0c;包括强大的AI运算&#xff0c;12 TOPS 算力和计算机图形处理能力&#xff0c;可轻松创造涵盖机器人、企业、工业和自动化等…

【nginx 第一篇章】认识一下 NGINX 服务器

一、简介 Nginx (engine x) 是一个高性能的 HTTP 和反向代理服务器&#xff0c;也是一个 IMAP/POP3/SMTP 代理服务器。由俄罗斯程序员 Igor Sysoev 开发&#xff0c;并在2004年首次公开发布。Nginx 以其高并发处理能力、低内存消耗、稳定性、丰富的功能集、简单的配置以及低学…

HarmonyOS应用三之组件生命周期和参数传递

目录&#xff1a; 1、生命周期的执行顺序2、页面数据传递3、图片的读取4、数据的备份和恢复5、轮播图6、页面布局图 1、生命周期的执行顺序 /** Copyright (c) 2023 Huawei Device Co., Ltd.* Licensed under the Apache License, Version 2.0 (the "License");* yo…

html+css 实现hover 换背景跳动按钮

前言:哈喽,大家好,今天给大家分享html+css 实现hover 换背景跳动按钮!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦 💕 目录 📚一、效果📚二、原理解析💡这个按钮hover后,有4个变化:📝1.1…

⼆叉树选择题

⼆叉树选择题 本篇文章是初阶二叉树的收尾&#xff0c;旨在进一步加深对于二叉树性质的理解&#xff0c;祝你有一个愉快的学习之旅&#xff01; &#x1f4a1; ⼆叉树性质 1&#xff09;对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分⽀结点个数为 n2 ,则有…

Java 阿里云视频直播开发流程

首先来看一下直播效果 推流工具有很多种&#xff08;例如OBS、阿里云直播Demo推流、等等&#xff0c;我用的是芯象导播&#xff09;阿里播放器地址 一、直播基础服务概述 官方文档说明 二、直播域名配置需要两个域名&#xff08;推流域名、播流域名&#xff09; 官方文档说…

haproxy七层代理总结

一、HAProxy概念 1.1 什么是HAProxy&#xff1f; HAProxy是一款开源、高性能的负载均衡器和代理服务器&#xff0c;专为TCP和HTTP应用而设计。它可以将客户端的请求分发到多台后端服务器&#xff0c;从而提高应用的可用性和性能。HAProxy支持多种负载均衡算法和健康检查机制&a…

Python 3 入门基础知识【3】递归函数以及参数部分

在编码过程中除了使用Python内置的函数以外&#xff0c;我们也经常需要自己定义函数。今天来回顾python中的函数。 目录 1.定义函数 2.中函数的返回值 3.递归函数 4.Python函数参数 5.Python函数使用默认参数 6.Python函数使用可变参数 7.Python函数使用可变关键字参数 …

针对thinkphp站点的漏洞挖掘和经验分享

0x1 前言 浅谈 目前在学习和研究thinkphp相关漏洞的打法&#xff0c;然后最近对于thinkphp资产的收集方面有了一个简单的认识&#xff0c;然后写一篇新手看的thinkphp相关的漏洞收集和挖掘的文章来分享下。然后后面是给师傅们分享下后台文件上传&#xff0c;然后直接打一个ge…

WPF 资源、引用命名空间格式、FrameworkElement、Binding、数据绑定

资源 对象级别独立文件 静态资源使用(StaticResource)指的是在程序载入内存时对资源的一次性使用&#xff0c;之后就不再去访问这个资源了。 动态资源使用&#xff08;DynamicResource&#xff09;使用指的是在程序运行过程中仍然会去访问资源。 显然&#xff0c;如果你确定…

欧阳坚持每周一篇高质量文章,半年后收入1380.27元

前言 大家好&#xff0c;我是欧阳&#xff0c;到目前为止欧阳已经坚持连续高质量周更文章7个多月了。在第6个月时就想写一篇半年总结&#xff0c;但是因为拖延症直到现在才写这篇半年复盘文章。 我的成果 先来说一下连续周更半年取得的成果&#xff0c;分别是收入1380.27元、…

redis模块和ioredis的注意事项

redis模块和ioredis的注意事项 文章目录 redis模块和ioredis的注意事项前言一、ioredis和redis使用zrange的比较二、出现zrange结果不同的原因总结 前言 node.js在使用redis的时候有两个库可以选择&#xff0c;一个是redis、另一个是ioredis&#xff0c;我一直以来也没有太大关…

LeetCode之回溯

1.全排列 1.1 题目 1.2 题解 LeetCode 力扣官方题解 1.3 代码 class Solution {public List<List<Integer>> permute(int[] nums) {// 创建一个空的列表 res&#xff0c;用于存储所有的排列结果List<List<Integer>> res new ArrayList<>();/…

练习题PHP5.6+变长参数 ⇒ usort回调后门 ⇒ 任意代码执行

突破长度限制 使用usort上传后门 usort — 使用用户自定义的比较函数对数组中的值进行排序 paramusort(...$GET); ...为php设置可变长参数 在url地址栏中输入[]test&1[]phpinfo();&2assert 包含了phpiinfo&#xff08;&#xff09;命令执行 结合usort使用 assert…

SpringMVC快速入门

MVC模式 MVC&#xff08;Model-View-Controller&#xff09;模式是一种设计模式&#xff0c;用于分离应用程序的不同方面&#xff0c;以提高代码的组织性和可维护性。在Spring MVC框架中&#xff0c;MVC模式的作用是将应用程序的不同职责分开&#xff0c;从而简化开发和维护过…

Datawhale X 魔搭 AI夏令营第四期 AIGC方向 task02笔记

AI工具使用 1. baseline 代码2. 使用通义千问理解代码2.1 工作流程2.2 逐行释意 3. 使用通义千问生成 Prompt3.1 生成的 Prompt3.1 根据 Prompt 生成的图片 1. baseline 代码 !pip install simple-aesthetics-predictor!pip install -v -e data-juicer!pip uninstall pytorch-…

EasyBoss ERP上线TikTok热销数据功能,助力TikTok本土店卖家快速选品上货!

想要你的TikTok本土小店销量不断增长&#xff0c;选品至关重要。只有选品问题解决了&#xff0c;后续的投放、小店定调等动作才有意义。 因此&#xff0c;今天就来分享几种TikTok本土小店的选品策略。 一、TikTok Shop选品的底层逻辑 图源&#xff1a;TikTok Shop 在选品之前…

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…

C++哪些变量在没有显式初始化的情况下会被初始化为0

首先&#xff0c;我们需要明白C程序编译链接后会包含以下几个主要段(Section)。 代码段(.text)&#xff1a;存放程序的可执行代码&#xff0c;通常是只读的数据段(.data)&#xff1a;存放已初始化的全局变量和静态变量BSS段(.bss)&#xff1a;存放未初始化的全局变量和静态变量…