首页 > 其他分享 >Hash表实践 —— 两数之和

Hash表实践 —— 两数之和

时间:2024-09-13 10:25:41浏览次数:12  
标签:map Hash index 步骤 个数 实践 num 补数 两数

目录


题目背景

image

这个题目用常规的双循环就可以完成。
但不是最优解。为什么?

看看他的步骤数:
N =【3,2,4】
求结果为6的两个元素坐标如下,
1). 3+2 = 5 不等于
2). 3+4 = 7 不等于
3). 2+4 = 6 等于,获取坐标【1,2】

规律:
2个数 = 1 个步骤
3个数 = 3 个步骤
4个数 = 6 个步骤
5个数 = 10 个步骤
6个数 = 15 个步骤
7个数 = 21 个步骤
......

如果有N个元素, 则需要N个步骤,那么记作 O(N)。下面分析那么这个算法的大O是:
image

约等于 N(N) = $ N^2 $

这个算法的时间复杂度为:O($ N^2 $).
有什么办法能降低这个时间复杂度吗?

解题思路

image

def twoSum(nums, target):
    # 创建一个哈希表来存储值和索引
    num_to_index = {}

    # 遍历数组
    for i, num in enumerate(nums):
        # 计算当前数字的补数
        complement = target - num

        # 检查补数是否在哈希表中
        if complement in num_to_index:
            # 如果在,返回补数的索引和当前索引
            return [num_to_index[complement], i]

        # 如果不在,将当前数字及其索引存入哈希表
        num_to_index[num] = i

    # 如果没有找到符合条件的两个数,返回空列表或抛出异常
    return []

print(twoSum([3, 2, 4], 6))

模拟运行过程:

# {} 创建map

# 1) 6 - 3 = 3 , 判断 3不在map,继续
# map加上{3:1}

# 2) 6 - 2 = 4 , 判断 4不在map,继续
# map加上{3:1,2:2}

# 3) 6 - 4 = 2 , 判断 2在map ,返回当前4和2的坐标,结束。
# map{3:1,2:2}

标签:map,Hash,index,步骤,个数,实践,num,补数,两数
From: https://www.cnblogs.com/mysticbinary/p/18389836

相关文章

  • 视频监控平台是如何运作的?EasyCVR视频汇聚平台的高效策略与实践
    随着科技的飞速发展,视频监控平台在社会安全、企业管理、智慧城市构建等领域发挥着越来越重要的作用。一个高效的视频监控平台,不仅依赖于先进的硬件设备,更离不开强大的视频处理技术作为支撑。这些平台集成了多种先进的视频技术,以确保实时监控、智能分析、高效传输和存储。今天我们......
  • 黑马面试集合(ArrayList, HashMap)篇笔记整理,结尾附Java的集合相关高频面试题及答案
    集合操作数据的特点-算法复杂度分析数据结构算法复杂度分析为什么要进行复杂度分析?指导编写性能更优的代码评判别人写代码的好坏时间复杂度分析时间复杂度分析:来评估代码的执行耗时的假设每行代码的执行耗时一样:1ms分析这段代码一共执行多少行?3n+3......
  • LinkedHashMap原理详解—从LRU缓存机制说起
    写在前面从一道Leetcode题目说起首先,来看一下Leetcode里面的一道经典题目:146.LRU缓存机制,题目描述如下:请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类:LRUCache(intcapacity)以正整数作为容量capacity初始化LRU缓存intget(int......
  • 使用信号量实现限流器:Python 实践指南
    使用信号量实现限流器:Python实践指南在现代应用程序中,限流器(RateLimiter)是一个非常重要的组件。它可以帮助我们控制对资源的访问频率,防止系统过载,确保服务的稳定性。本文将详细介绍如何使用Python中的信号量(Semaphore)来实现一个高效的限流器。什么是限流器?限流器是一......
  • 线程---实践与技巧(C语言)
            目录一、引言二、线程基础  1.线程概念  2.线程库三、线程的创建与终止  1.创建线程  2.终止线程四、线程同步与互斥  1.互斥锁(Mutex)  2.条件变量(ConditionVariable)五、线程间的通信六、总结               ......
  • 云监控治理检测:云监控的自助化最佳实践
    概述在数字化转型浪潮中,云计算技术已成为企业实现敏捷性和创新的重要工具。作为全球领先的云服务提供商,阿里云在帮助企业实现高效云管理方面发挥着重要作用。然而,随着云环境的日益复杂化和规模的不断扩大,如何有效管理和监控云资源,确保其高效、安全、合规地运行,成为企业面临的挑......
  • HashMap线程不安全|Hashtable|ConcurrentHashMap
    文章目录常见集合线程安全性HashMap为什么线程不安全?怎么保证HashMap线程安全HashtableConcurrentHashMap引入细粒度锁代码中分析总结小结常见集合线程安全性ArrayList、LinkedList、TreeSet、HashSet、HashMap、TreeMap等都是线程不安全的。HashTable是线程安......
  • Nginx入门实践(四)
    环境系统:Windows7Nginx版本:1.26.2Nginx负载均衡实现实现逻辑Nginx1:访问入口Nginx2、Nginx3、Nginx4:组成负载集群配置C:\Windows\System32\drivers\etc\hosts文件新增IP域名映射127.0.0.1backend1.com127.0.0.1backend2.comNginx1配置http{ upstreambacke......
  • HashMap源码分析
    HashMap源码分析在jdk1.8中,HashMap的数据结构如上图所示,是由Node数组+链表/红黑树组成的,每个K-V对保存在一个Node结点中,看一下Node结点的定义,其实就是一个Map.Entry<K,V>的实现类,包括key的hash值,key,value和一个next指针。staticclassNode<K,V>implementsMap.Entry<K,V>{......
  • 影刀RPA与WPS文档协同办公:实现高效自动化处理的策略与实践
    摘要随着数字化转型的深入,企业对于办公自动化的需求日益增长。影刀RPA(RoboticProcessAutomation)与WPS文档的协同办公提供了一种高效、自动化的解决方案。本文旨在探讨影刀RPA与WPS文档如何配合使用,以实现工作流程的自动化,提高办公效率,并为企业带来实际效益。引言影刀R......