leedcode-哈希表篇(1)

1.两数之和

题目

给定一个整数数组nums和一个整数目标值target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案
示例1:

输入:nums=[2,7,11,15],target=9
输出:【0,1】
解释:nums[0]+nums[1]==9 返回【0,1】

此处如果用之前指针篇的方法,显然会不太适合,因为这里的数组不是全都有序,因此如果用双指针会对无序数组无效,就是移动的规则无法定下来。因此借助哈希表进行操作,我一开始不是很知道哈希表是什么东西,后来一看答案,哦~原来是字典。

class Solution:
	def twoSum(self,nums:List[int],target:int)->List[int]:
		hash_map={}
		for i in range(len(nums)):
			t=target-nums[i]
			if t not in hash_map:
				hash_map[nums[i]]=i
			else:
				return [hash_map[t],i]

思路就是找出target和待查数组元素中的差距,然后遍历这种差距值在除了待查数组元素外还是否存在其他的元素。而且根据题目所示每个元素不能遍历两次。那么具体的操作是:拿出第一个元素,然后和target相减,将这个差值拿去字典遍历,如果它不在字典里面,那么就将第一个元素的值作为key,这个元素的下标作为value存到哈希表里面,然后在数组中拿出第二个元素7,然后target-7=2,此时发现2是在哈希表里面,那么就此时的第二个元素的下标,以及t在哈希表里面对应的value,也就是它在原数组的下标一起返回

测试用例

def twoSum(nums,target):
	hash_map={}
	for i in range(len(nums)):
		t=target-nums[i]
		if t not in hash_map:
			hash_map[nums[i]]=i
			print(hash_map)
		else: 
			print(hash_map)
			return [i,hash_map[t]]
	
nums=[2,7,11,15]
print(twoSum(nums,9))
上一篇:leedCode 4寻找两个正序数组的中位数


下一篇:数据库连接池DBCP浅析