首页 > 其他分享 >两数之和【哈希】

两数之和【哈希】

时间:2024-01-08 16:37:33浏览次数:33  
标签:target nums int 复杂度 hashTable 哈希 两数


Problem: 1. 两数之和


文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code


思路

n方可以暴力,也可以用hash去降低时间复杂度。

解题方法

遍历列表,每个数都看一下是否它的补是否再hash表里面,在就说明找到了,不在就把它放进去,然后继续遍历。

复杂度

时间复杂度:

添加时间复杂度, 示例: 两数之和【哈希】_空间复杂度

空间复杂度:

添加空间复杂度, 示例: 两数之和【哈希】_空间复杂度

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashTable = dict();
        for i in range(len(nums)):
            if target - nums[i] in hashTable:
                return [hashTable[target - nums[i]], i]
            else:
                hashTable[nums[i]] = i


标签:target,nums,int,复杂度,hashTable,哈希,两数
From: https://blog.51cto.com/u_15714381/9146665

相关文章

  • 字符串和哈希表的基本用法总结
    2287.重排字符形成目标字符串解决代码classSolution{publicintrearrangeCharacters(Strings,Stringtarget){Map<Character,Integer>sCounts=newHashMap<Character,Integer>();Map<Character,Integer>targetCounts=newHashMap&......
  • 网络攻防技术——哈希碰撞
    实验3:MD5碰撞试验实验内容:本次实验主要是加深大家对MD5碰撞及其原理的理解,使用SEED实验环境中的工具及编程语言,完成以下任务:使用md5collgen生成两个MD5值相同的文件,并利用bless十六进制编辑器查看输出的两个文件,描述你观察到的情况;参考Lab3_task2.c的代码,生成两个MD5值相同但......
  • leetcode 2.两数相加
    leetcode第二题:两数相加以链表为载体模仿加法进位,同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个0。如果链表遍历结束后,有carry>0,还需要在答案链表的后面附加一个节点,节点的值为carry。易错点:1.......
  • 哈希冲突
    我们先模拟一下,其实题目就是要我们从\(y\)这个位置开始跳,每次跳\(x\)步,然后把每次跳到的数的和加起来就是最终的答案我们发现当\(x\)比较大的时候是可以暴力的,但是比较小的时候就不行了这时就有一个套路了,我们找出一个分界点,比这个分界点大的时候我们暴力否则使用其他方法那么......
  • leetcode 1.两数之和
    leetcode第一题:两数之和1.暴力枚举:最容易想到的方法是枚举数组中的每一个数x,寻找数组中是否存在target-x。当我们使用遍历整个数组的方式寻找target-x时,需要注意到每一个位于x之前的元素都已经和x匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们......
  • 深入浅出一致性哈希
    哈希是什么哈希又称散列,是一种计算数据指纹的方法。哈希函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来业务场景常见的业务场景;网站用户请求后,为了性能一般都会加一层缓存。缓存有多个节点,每个节点存储了不同数据。获取数据,先根据数据取模(哈希)找到缓存节点......
  • 哈希集合、哈希表的拉链法实现
    哈希表705.设计哈希集合//拉链法structListNode{intval;structListNode*next;};typedefstruct{structListNode*data;}MyHashSet;//模constinthashSize=1009;MyHashSet*myHashSetCreate(){MyHashSet*myHashSet=(MyHashSet......
  • C#深度理解:数组、集合、哈希、字典、堆、栈 优缺点
    一、数组1、Array固定数组优点:1).快速访问:数组通过索引来访问元素,访问速度非常快,因为可以通过索引进行直接定位。2).内存连续存储:数组在内存中以连续的方式存储元素,这样有助于提高数据的读取和写入效率。3).多维支持:C#中的数组支持多维(二维、三维等)数据结构,可以用于表示......
  • 关于密码哈希算法BCrypt的编码结果各部分意义分析及其他注意事项
    找到一个英文的解析:Thebcryptstandardmakesstoringsaltseasy-everythingitneedstocheckapasswordisstoredintheoutputstring.Theprefix"$2a$"or"2y"inahashstringinashadowpasswordfileindicatesthathashstringisabcr......
  • [转][译] 密码哈希的方法:PBKDF2,Scrypt,Bcrypt 和 ARGON2
    原文地址:PasswordHashing:PBKDF2,Scrypt,BcryptandARGON2原文作者:MichelePreziuso译文出自:掘金翻译计划本文永久链接:https://github.com/xitu/gold-miner/blob/master/TODO1/password-hashing-pbkdf2-scrypt-bcrypt-and-argon2.md译者:司徒公子校对者:xionglong58、GJX......