【收录 Hello 算法】10.4 哈希优化策略
目录
10.4 哈希优化策略
10.4.1 线性查找:以时间换空间
10.4.2 哈希查找:以空间换时间
10.4 哈希优化策略
在算法题中,我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。
Question
给定一个整数数组 nums 和一个目标元素 target ,请在数组中搜索“和”为 target 的两个元素,并返回它们的数组索引。返回任意一个解即可。
10.4.1 线性查找:以时间换空间
考虑直接遍历所有可能的组合。如图 10-9 所示,我们开启一个两层循环,在每轮中判断两个整数的和是否为 target ,若是,则返回它们的索引。

图 10-9 线性查找求解两数之和
代码如下所示:
two_sum.c
/* 方法一:暴力枚举 */
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {for (int i = 0; i < numsSize; ++i) {for (int j = i + 1; j < numsSize; ++j) {if (nums[i] + nums[j] == target) {int *res = malloc(sizeof(int) * 2);res[0] = i, res[1] = j;*returnSize = 2;return res;}}}*returnSize = 0;return NULL;
}
此方法的时间复杂度为 𝑂(𝑛2) ,空间复杂度为 𝑂(1) ,在大数据量下非常耗时。
10.4.2 哈希查找:以空间换时间
考虑借助一个哈希表,键值对分别为数组元素和元素索引。循环遍历数组,每轮执行图 10-10 所示的步骤。
- 判断数字
target - nums[i]是否在哈希表中,若是,则直接返回这两个元素的索引。 - 将键值对
nums[i]和索引i添加进哈希表。
<1><2><3>

图 10-10 辅助哈希表求解两数之和
实现代码如下所示,仅需单层循环即可:
two_sum.c
/* 哈希表 */
typedef struct {int key;int val;UT_hash_handle hh; // 基于 uthash.h 实现
} HashTable;/* 哈希表查询 */
HashTable *find(HashTable *h, int key) {HashTable *tmp;HASH_FIND_INT(h, &key, tmp);return tmp;
}/* 哈希表元素插入 */
void insert(HashTable *h, int key, int val) {HashTable *t = find(h, key);if (t == NULL) {HashTable *tmp = malloc(sizeof(HashTable));tmp->key = key, tmp->val = val;HASH_ADD_INT(h, key, tmp);} else {t->val = val;}
}/* 方法二:辅助哈希表 */
int *twoSumHashTable(int *nums, int numsSize, int target, int *returnSize) {HashTable *hashtable = NULL;for (int i = 0; i < numsSize; i++) {HashTable *t = find(hashtable, target - nums[i]);if (t != NULL) {int *res = malloc(sizeof(int) * 2);res[0] = t->val, res[1] = i;*returnSize = 2;return res;}insert(hashtable, nums[i], i);}*returnSize = 0;return NULL;
}
此方法通过哈希查找将时间复杂度从 𝑂(𝑛2) 降至 𝑂(𝑛) ,大幅提升运行效率。
由于需要维护一个额外的哈希表,因此空间复杂度为 𝑂(𝑛) 。尽管如此,该方法的整体时空效率更为均衡,因此它是本题的最优解法。
相关文章:
【收录 Hello 算法】10.4 哈希优化策略
目录 10.4 哈希优化策略 10.4.1 线性查找:以时间换空间 10.4.2 哈希查找:以空间换时间 10.4 哈希优化策略 在算法题中,我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。 Question 给…...
浅析部署架构中的GZone、RZone和CZone
在现代软件开发中,理解和应用各种技术概念是成功的重要因素。本文将详细介绍GZone、RZone和CZone三个概念,解释它们的定义、特点、功能及应用场景,并通过实际案例帮助读者更好地理解这些概念。 一、GZone 1.1 定义 GZone是指“Global Zone…...
【全开源】分类记账小程序系统源码(ThinkPHP+FastAdmin+UniApp)
基于ThinkPHPFastAdminUniAppvk-uView-uiVue3.0开发的一款支持多人协作的记账本小程序,可用于家庭,团队,组织以及个人的日常收支情况记录,支持周月年度统计。 :智能管理您的财务生活 一、引言:财务智能化…...
Android NDK系列(四)NDK的编译
Native工程一般会用到NDK,一般开发者使用的NDK是官方提供的,直接下载即可使用。在工作过程中一般很少要定义NDK,不过对于想了解NDK是怎么生成的,可以继续往下阅读。 Google提供了编译NDK的说明文档,地址为NDK编译&…...
Jenkins--从入门到入土
Jenkins–从入门到入土 文章目录 Jenkins--从入门到入土〇、概念提要--什么是CI/DI?1、CI(Continuous Integration,持续集成)2、DI(DevOps Integration,DevOps 集成)3、解决的问题 一、Jenkins安…...
文心一言 VS 讯飞星火 VS chatgpt (267)-- 算法导论20.2 2题
二、写出 PROTO-vEB-DELETE 的伪代码。通过扫描簇内的相关位,来更新相应的 summary 位。并且你实现的伪代码的最坏情况运行时间是多少?如果要写代码,请用go语言。 文心一言: 首先,让我们回顾一下vEB(Van …...
C 语言设计模式(结构型)
文章目录 代理模式场景示例 门面模式场景示例 桥接模式场景示例 适配器模式场景示例 外观模式场景示例 享元模式场景示例 装饰器模式场景示例 组合模式场景示例 代理模式 C语言中,代理模式通常用于实现对象的间接访问。代理模式是一种结构型设计模式,它…...
【云原生--K8S】K8S python接口研究
文章目录 前言一、搭建ubuntu运行环境1.运行ubuntu容器2.拷贝kubeconfig文件二、python程序获取k8s信息1.获取node信息2.获取svc信息3.常用kubernetes API总结前言 在前面的文章中我们都是通过kubectl命令行来访问操作K8S,但是在实际应用中可能需要提供更方便操作的图形化界面…...
5.26作业
服务器 2 3 #define BUFSIZE 10244 #define login_msg_len 205 6 typedef struct Node{7 char name[login_msg_len];8 struct sockaddr_in addr;9 struct Node *next;10 }Node;11 12 typedef struct Msgtype{13 char type;14 char username[login_msg_len]…...
链接库文件体积优化工具篇:bloaty
笔者之前参与过一个嵌入式智能手表项目,曾经碰到过这样一个问题:手表的flash大小只有2M,这意味着只能在上面烧录2M大小的代码。随着开发不断进行,代码越写越多,编译出来的bin也越来越大。最后bin大小超过了2M, 就没法烧…...
使用pyqt绘制一个爱心!
使用pyqt绘制一个爱心! 介绍效果代码 介绍 使用pyqt绘制一个爱心! 效果 代码 import sys from PyQt5.QtWidgets import QApplication, QMainWindow, QWidget from PyQt5.QtGui import QPainter, QPen, QBrush, QColor from PyQt5.QtCore import Qt, Q…...
关于 Transformer 的11个常见面试题
Transformer 是如何工作的? Transformer 是一种深度学习算法,特别适用于自然语言处理(NLP)任务,如语言翻译、语言生成和语言理解。它们能够处理长度可变的输入序列并捕捉长距离依赖关系,使其在理解和处理自…...
OS多核多线程锁记录笔记
自旋锁作用 自旋锁的是为了保护两个核上的公共资源,也就是全局变量,只有在一方也就是一个核抢到了自选锁,才能对公共资源进行操作修改,当然还有其他形似的锁如互斥锁,这里不比较两者的区别,以前没有深入的去…...
nginx做TCP代理
要实现TCP代理,可以使用Nginx的stream模块。stream模块允许Nginx作为一个转发代理来处理TCP流量,包括TCP代理、负载均衡和SSL终止等功能。 以下是配置Nginx实现TCP代理的基本步骤: 在Nginx配置文件中添加stream块,并在该块中配置…...
python 异常处理 try
异常 我们常见的代码错误后 会出现此类异常 SyntaxError:语法错误 AttributeError:属性错误 IndexError:索引错误 TypeError:类型错误 NameError:变量名不存在错误 KeyError:映射中不存在的关键字…...
月入10万+管道收益,揭秘旅游卡运营的5个阶段!
网上的项目众多,只要用心,便能发现不少商机。在互联网上运营,关键在于理解项目的底层逻辑。今天,我们来揭秘旅游卡项目,如何做到月入10万。 1、先赚成本 开始项目时,首要任务是回本。不要急于求成&#x…...
android_binder源码分析之_binder驱动使用服务
一,binder驱动源码分析,使用服务过程 uint32_t svcmgr_lookup(struct binder_state *bs, uint32_t target, const char *name) {uint32_t handle;unsigned iodata[512/4];struct binder_io msg, reply;bio_init(&msg, iodata, sizeof(iodata), 4);b…...
【波点音乐看广告】
import uiautomator2 as u2 import time from datetime import datetime import xml.etree.ElementTree as ET import re import os 连接设备 d u2.connect() os.system(‘adb shell chmod 775 /data/local/tmp/atx-agent’) os.system(‘adb shell /data/local/tmp/atx-age…...
[SWPUCTF 2021 新生赛]pop
常见的魔术方法 魔术方法__construct() 类的构造函数,在对象实例化时调用 __destruct() 类的析构函数,在对象被销毁时被调用 __call() 在对象中调用一个不可访问的对象时被调用,比如一个对象被调用时,里面没有程序想调用的属性 …...
【DevOps】Jenkins + Dockerfile自动部署Maven(SpringBoot)项目
环境 docker_host192.168.0.1jenkins_host192.168.0.2 jenkins_host构建完成后把jar发布到docker_host,再通过dockerfile自动构建镜像,运行镜像 1 Jenkins安装 AWS EC2安装Jenkins:AWS EC2 JDK11 Jenkins-CSDN博客 AWS EC2上Docker安装…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
