python 两数之和 ,数组,哈希表
时间: 2024-05-25 22:18:06 浏览: 16
题目描述:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路:
方法一:暴力枚举
最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target - x。
时间复杂度:O(n^2),对于每个元素,都需要遍历一遍数组。
方法二:哈希表
通过哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(n) 降低到 O(1)。
我们每次将 x 插入到哈希表中,然后寻找 target - x 是否在哈希表中即可。
时间复杂度:O(n),遍历一遍数组即可寻找到答案。
Python 代码:
相关问题
python用哈希表计算数组中唯一值的和
可以使用Python内置的set()函数来实现哈希表计算数组中唯一值的和。具体步骤如下:
1. 首先定义一个数组arr,包含一些整数值。
2. 使用set()函数将数组转化为一个集合set_arr,这样就可以去掉数组中的重复项。
3. 遍历集合set_arr中的所有元素,并将它们累加到变量sum中。
4. 最后输出变量sum的值,即为数组中唯一值的和。
下面是Python代码示例:
```python
arr = [1, 2, 3, 4, 2, 3, 5, 6, 1]
set_arr = set(arr)
sum = 0
for num in set_arr:
sum += num
print(sum)
```
输出结果为:21,即数组中唯一值的和。
最长无重复子数组哈希表解题
最长无重复子数组问题可以用哈希表来解决。具体思路如下:
1. 定义一个哈希表,用于记录每个元素最后一次出现的位置。
2. 定义两个指针i和j,分别指向子数组的起始位置和结束位置。
3. 遍历数组,对于每个元素num,如果其不在哈希表中,或者其在哈希表中的位置小于i,则更新哈希表中num的位置为当前位置。
4. 如果num在哈希表中,并且其在哈希表中的位置大于等于i,则更新i为num在哈希表中的位置加1。
5. 在每次更新i和j后,计算当前子数组的长度,并与之前的最大长度进行比较,更新最大长度。
6. 最终得到的最大长度即为所求。
下面是Python代码实现:
```python
def longest_subarray(nums):
max_len = 0
hash_table = {}
i = 0
for j in range(len(nums)):
if nums[j] not in hash_table or hash_table[nums[j]] < i:
hash_table[nums[j]] = j
else:
i = hash_table[nums[j]] + 1
hash_table[nums[j]] = j
max_len = max(max_len, j - i + 1)
return max_len
```
该算法的时间复杂度为O(n),空间复杂度为O(n)。