Leetcode 0001 两数之和（哈希数组）

曾经终败给现在 2024-05-08 06:35 27阅读 0赞

#### 目录 ####

*  题目描述
 *  样例
 *  思路
 *  复杂度
 *  代码

## 题目描述 ##

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

## 样例 ##

示例 1：

输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
    输出：[1,2]

## 思路 ##

用一个哈希表存储出现过的数字及其下标，其中key为数字，value为其对应的下标  
遍历nums中每一个数，判断target-num是否出现过  
如果出现，则表示查找成功，返回结果  
如果未出现，则将该数放入字典中

## 复杂度 ##

时间复杂度：O(n) 因为使用了hash表，所以查找时是O(1)的，但需要遍历整个数组  
空间复杂度: O(n) 需要存储所有的元素

## 代码 ##

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            # 初始化字典，key为数值，value为下标
            hashRecord = dict()
            for i, num in enumerate(nums):
                r = target - num
                # 判断r是否出现在hash数组中
                if r in hashRecord:
                    return [hashRecord[r], i]  # 返回前一个数的下标和当前数的下标
                hashRecord[num] = i  # python的字典如果没有对应的key则加一个
            return []

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 0001 两数之和（哈希数组）

目录题目描述样例思路复杂度代码题目描述给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回...

曾经终败给现在/ 2024年05月08日 06:35/ 0 赞/ 28 阅读

相关 LeetCode_双指针_哈希表_简单_1.两数之和

目录 1.题目 2.思路 3.代码实现（Java） 4.扩展 1.题目给定一个整数数组 nums 和一个整数目标值 target，请你在

浅浅的花香味﹌/ 2023年10月06日 17:57/ 0 赞/ 10 阅读

相关 1. 两数之和（数组+哈希表）

1.题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一

超、凢脫俗/ 2022年12月04日 09:14/ 0 赞/ 97 阅读

相关【数组】两数之和

[【2020秋招-面试题目汇总（随时更新）】][2020_-] 1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naG

小鱼儿/ 2022年11月26日 07:56/ 0 赞/ 116 阅读

相关 Two Sum (两数之和) - Hash Table (哈希表)

Two Sum (两数之和) - Hash Table (哈希表) [https://leetcode-cn.com/problems/two-sum/][https_l

电玩女神/ 2022年10月10日 14:52/ 0 赞/ 114 阅读

相关 LeetCode 两数之和—利用哈希表的经典案例

前言给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种

╰半橙微兮°/ 2022年10月06日 02:58/ 0 赞/ 74 阅读

相关 Leetcode刷题100天—1. 两数之和(数组+哈希表)—day23

前言： > 作者：神的孩子在歌唱 > > 大家好，我叫运智 ![image-20210830202452688][] [1. 两数之和][1.] 难度简单1196

桃扇骨/ 2022年09月11日 14:28/ 0 赞/ 110 阅读

相关 LeetCode 两数之和、三数之和

1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。你可以假设每种输入只会对应一个答案。但是，你不能重复

旧城等待，/ 2022年04月13日 05:42/ 0 赞/ 247 阅读

相关 Leetcode两数之和数组——C

来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/two-sum][https_leetcode-cn.com_pr

朱雀/ 2022年01月05日 11:51/ 0 赞/ 167 阅读

相关 LeetCode 1. 两数之和【数组 + 哈希表】 C++ 和 Java版题解

[LeetCode 1. 两数之和][LeetCode 1.] 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，

男娘i/ 2021年07月25日 01:45/ 0 赞/ 258 阅读