01_哈希_简单_0001_两数之和_230727.md

[toc]

一、题目描述

题目链接

给定一个整数数组 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]

示例 3：

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

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

二、我的题解

两层for循环暴力求解

Parthenon程序

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(0,n):
            for j in range(i+1,n):
                if nums[i] + nums[j] == target:
                    return [i, j]

复杂度分析

• 时间复杂度：$O(N^2)$

• 空间复杂度：==待补充==

思考与收获

len()函数返回列表中元素的个数

range(0, n) 中包含的值依次为 0, 1, ...,n-1

返回值为列表，不需要写List定义， return [i, j]即可

for 循环时循环变量不需要定义

注意区分 C++ 和 python 的不同的编程习惯

时间复杂度和空间复杂度分析下一题加强

程序中list和List有什么区别？

区别在于 list 是实际的数据类型，而 List 是用于类型提示的类。我们可以使用 list 来创建、操作实际的列表对象，而 List 用于在类型提示中指示函数参数或返回值应该是列表类型

怎么自己写输入输出？

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #暴力循环模式
        n = len(nums)
        for i in range(0,n):
            for j in range(i+1,n):
                if nums[i] + nums[j] == target:
                    return [i, j]

def test_two_sum():
    nums = list(map(int,input("输入整数数组:").split()))
    target = int(input("输入目标值:"))

    solution = Solution()
    result = solution.twoSum(nums,target)

    print("结果：",result)

if __name__ == "__main__":
    test_two_sum()

• input和print的用法
• 标准的python程序结构

哈希表-索引作字典值

python3程序

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #哈希表解题
        hashtable = {}
        for index,val in enumerate(nums):
            if target - val not in hashtable:
                hashtable[val] = index
            else:
                return [hashtable[target - val],index]

复杂度分析

• 时间复杂度:$O(N)$
• 空间复杂度：==待补充==

思考与收获

什么是哈希表？

定义

哈希表是一种常用的数据结构，也称为散列表。它通过将键（Key）映射到值（Value）来实现高效的数据查找和插入操作。在哈希表中，键和值之间建立了一种映射关系，通过一个哈希函数将键映射到一个唯一的索引位置，这样就可以在常数时间内（即 O(1) 时间复杂度）查找或插入值。

哈希表的工作原理

哈希表的核心是哈希函数。哈希函数将键转换为一个整数，这个整数称为哈希值或哈希码。哈希值作为数组的索引，用于快速定位存储和检索值。理想情况下，每个键都会被映射到不同的哈希值，这样可以避免哈希冲突，保证查找效率。

Python 中的哈希表实现

在 Python 中，哈希表的主要实现是使用字典（Dictionary）。Python 的字典是一个无序的键值对集合，其中的键必须是唯一的，而值可以是任意类型的数据。字典的内部实现就是基于哈希表。

创建字典

可以使用花括号 {} 或 dict() 函数来创建字典。示例如下：

# 使用花括号创建字典
my_dict = {'apple': 1, 'banana': 2, 'orange': 3}

# 使用 dict() 函数创建字典
my_dict = dict(apple=1, banana=2, orange=3)

插入和访问元素

可以使用键来插入和访问字典中的元素。示例如下：

# 插入元素
my_dict['grape'] = 4

# 访问元素
print(my_dict['apple'])  # 输出: 1
print(my_dict['grape'])  # 输出: 4

删除元素

可以使用 del 关键字来删除字典中的元素。示例如下：

# 删除元素
del my_dict['banana']

哈希表的查找时间复杂度

在理想情况下，哈希表的查找时间复杂度是 $O(1)$，也就是常数时间。但在某些情况下，由于哈希冲突等原因，查找时间可能会变为 $O(n)$，其中 $n$ 是哈希表中键值对的数量。

enumerate的用法？

在 Python 中，enumerate 是一个内置函数，用于将一个可迭代对象（如列表、元组、字符串等）组合为一个索引序列，同时返回元素和对应的索引。它常用于循环遍历时需要同时访问元素和索引的情况。

enumerate 函数的语法如下：

enumerate(iterable, start=0)

参数说明：

• iterable：要进行枚举的可迭代对象，可以是列表、元组、字符串等。
• start：可选参数，表示开始计数的起始值，默认为 0。如果指定了 start，那么索引从 start 开始，否则从 0 开始。

enumerate 函数返回一个迭代器，该迭代器依次包含元组，每个元组包含两个值：索引和对应的元素。在循环遍历时，可以通过解构元组来获取元素和索引。

例子：

fruits = ['apple', 'banana', 'orange']

for index, fruit in enumerate(fruits):
    print(index, fruit)

输出：

0 apple
1 banana
2 orange

在上面的例子中，我们使用了 enumerate 函数遍历了 fruits 列表，并在循环中获取了每个水果的索引和名称。

if value not in hashtable的用法？

如果value不在哈希表中，则将value以及对应的index添加到哈希表中，供下次查找。

hashtable中谁做键谁做值？