leetcode hot100 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 题解
1.暴力解法
遍历每一对有可能的数对，遍历方法是第一个指针从1到n-1（数组长度）移动，每遍历一个数，就寻找其后数组里存不存在目标值-当前值，存在就返回，不存在继续移动指针
class Solution():def twoSum(self, nums, target):# 给定一个整数数组，和一个目标值# 遍历整个整数数组，算出目标值-当前值# 在其后的整数数组里搜索存不存在length = len(nums)for i in range(length):now = nums[i]tar = target - nowfor j in range(i+1,length):if nums[j]==tar:return [i,j]return []2.哈希表法
暴力解法的时间复杂度为o(n^2)，主要是他没有用上算出的目标值-当前值，如果以哈希表或者说在python中以字典的形式存储每次计算的值，则就无需每次计算，则是后发寻找即可，这样时间复杂度为o(n)。
class Solution():def twoSum(self, nums, target):# 给定一个整数数组，和一个目标值# 遍历整个整数数组，算出目标值-当前值# 如果这个值在hash表中，返回索引# 如果不在，存储当前值和索引到hash表中hash = {}n = len(nums)for i in range(n):if target-nums[i] in hash:return [hash[target-nums[i]],i]hash[nums[i]]=ireturn []3.有序组的前提（刚看到，这个属于leetcode167题，返回索引加1即可）
如果数组是有序的，那么对数组头和尾求和，如果大于目标值，说明只能减小其中一个数继续寻找（那自然只能减小大的那个）；如果大于目标值，那就需要增大小的那个；如果等于，查找结束。
这个题用不到这个思路，但是这种对于数组有序的情况很好用，记一下这个思路。还没看懂的话可以看这个视频
两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili
class Solution():def twoSum(self, nums, target):# 给定一个整数数组，和一个目标值# 遍历整个整数数组，算出目标值-当前值# 在其后的整数数组里搜索存不存在n = len(nums)low = 0high = n-1while low<high:if nums[low]+nums[high]==target:return [low,high]elif nums[low]+nums[high]>target:high -=1elif nums[low]+nums[high]<target:low +=1return []我的思考
这里补充一些我在这个题里涉及到的知识点
字典
很久没写python了，翻了翻菜鸟教程，这个题里有两个点需要注意，一个是新建字典，另一个是字典的键和值的区别
# 新建字典两个方法
hash = {}
hash = dict()# 键是唯一的，值是多样的，键可以索引值,值不能索引键
# 键的数据类型只能是数字或者字符串，值可以任意
# 所以我选择将数组的值设为hash的键，数组索引设为hash的值
# 字典初始化如下hash['1']='dog'哈希表
我用自己的话总结一下：哈希表本质就是一个存储空间+一个映射算法，完成了一个“每给定一个输入，就根据特定的算法将他映射入一个对应的地址中”，映射算法要保证1同一个输入每次映射到的地址是一样的，这样才可以查找2每个地址存储的数据均匀，都不是很多，这样方便高效查找。这样进行查找时，就不需要每个地址都查找，根据映射算法，查找对应地址即可。
类比一下，就是收作业时，给全班同学编号，然后让大家按序号交，1-9交在一起，10-19交在一起，20-29交在一起，这样，如果你需要查询25，你就不用全都遍历，只需要查看20那一堆，是不是搜索效率一下子就上升了。所以这个算法的设计就很重要，当然，这个就交给那些数学大神啦！
下面这个视频讲解了什么是哈希表
『教程』哈希表是个啥？_哔哩哔哩_bilibili
这个视频讲解为什么哈希表查找快
哈希表HashMap为何增删改查都很快（原理超简单）_哔哩哔哩_bilibili
为什么哈希表索引的很快（以下是deepseek的答案）
在 Python 3 中，字典（`dict`）的索引速度通常比数组（如 `list`）的查询速度快，这是因为它们的底层实现方式不同，导致了时间复杂度上的显著差异。以下是具体原因：
---
### 1. **数据结构与算法复杂度**
- **字典（`dict`）**：
- 基于**哈希表（Hash Table）**实现，通过哈希函数将键（key）映射到对应的值（value）。
- **平均时间复杂度为 O(1)**：无论字典规模多大，直接通过键查找值的时间几乎恒定（哈希冲突较少时）。
- **列表（`list`）**：
- 是基于连续内存的数组结构。
- **查找元素的时间复杂度为 O(n)**：如果通过值查询（如 `list.index(value)`），需要遍历整个列表；即使通过索引访问（如 `list[i]`），也只是 O(1)，但这不涉及“查询”过程。---
### 2. **哈希表的优势**
- **直接计算位置**：字典通过键的哈希值直接定位存储位置，无需遍历。
- **冲突处理**：即使发生哈希冲突（不同键映射到同一位置），Python 会通过开放寻址法等策略高效解决，保证操作速度。---
### 3. **列表的劣势**
- **顺序存储**：列表的查询（如判断 `x in list`）需要逐个比较元素，最坏情况下需检查所有元素。
- **无哈希优化**：列表的元素没有哈希机制支持，无法直接跳转到目标位置。---
### 4. **性能对比示例**
```python
# 字典查询（O(1)）
d = {"key1": 1, "key2": 2}
value = d["key1"] # 直接通过哈希定位# 列表查询（O(n)）
lst = [1, 2, 3, 4]
index = lst.index(3) # 需要遍历列表直到找到3
```---
### 5. **何时列表更快？**
- 如果通过**整数索引**访问（如 `lst[0]`），列表和字典的速度都是 O(1)，但列表可能略快（因内存连续，缓存友好）。
- 但若涉及**值查询**（如判断元素是否存在），字典的 O(1) 远胜列表的 O(n)。---
### 6. **其他注意事项**
- **字典的内存开销**：哈希表需要额外空间存储哈希值和解决冲突，因此内存占用比列表大。
- **键的唯一性**：字典要求键是可哈希的（如不可变类型：字符串、数字、元组等）。---
### 总结
字典的快速查询源于哈希表的高效设计，而列表的线性结构导致查询速度随规模增长下降。在需要频繁查找的场景中，字典是更优选择。