Python每日一练-----妈妈找小蝌蚪(哈希算法）
题目：
给定一个池塘里面有众多小蝌蚪（整数数组 nums） 他们已经排队好了，有一位青蛙妈妈（一个整数目标值 mom），请你帮助青蛙妈妈找到他的亲生孩子所在的位置（数组序号）（青蛙：生的时候我也没想过要找啊），假设青蛙妈妈身上又有一个整数mom，它的众多亲生孩纸身上也各有一个整数（有的娃拥有一样的数），但是生活压力太大了，青蛙妈妈只找两娃，这两小蝌蚪身上所带的整数相加正好等于青蛙妈妈身上的整数mom，且两个小蝌蚪所带整数不能一样。
例如
众多小蝌蚪所带整数构成的数组为： nums = [4, 5, 2, 1]
青蛙妈妈带有的目标值为：mom = 7
你需要找出两个娃：5， 2然后
返回他们所在位置 [ 1, 2 ]
众多小蝌蚪所带整数构成的数组为： nums = [4, 3, 3, 1]
青蛙妈妈带有的目标值为：mom = 6
你需要找出两个娃：3， 3然后
返回他们所在位置 [ 1, 2 ]而不能是[ 1, 1]或[ 2,2]因为他们是同一个娃
题目分析：给定一个目标数mom，在数组nums中找到两个数使它们相加等于mom，返回它们的位置，如果都不满足，无需输出，或者返回[]
老样子，第一感觉，暴力解题。
从数组nums中一个一个找，找出两数看它们相加是否为mom
def findChhild(nums, mom): n = len(nums) for i in range(n): for j in range(i + 1, n): # 从第二个位置出发避免重复 if nums[i] + nums[j] == mom: print([i, j])for j in range(i + 1, n): j 从 i 的后一个位置出发避免重复选择同一个娃，因为第一个 for 循环中i已经从第 i 个开始，那么 j 应从第 i 后一个位置开始，不然 i 和 j 可能是同一个娃（child）。
看着挺简短，实际运算时间为O(n^2)，算是比较慢的一种方法了。不过暴力解题往往较为直观。
现在优化一下，使用哈希算法
其实第一种办法花费时间长主要是寻找mom - child1太久了，不是找两数相加等于mom吗？为什么是mom - child1呢？先往下看。
首先我们可以创建一个哈希表，是不是感觉有点迷糊，其实哈希表就是一个散列表，也就是python所说的字典，不过这个字典内有乾坤，在此不展开讲了。（其实我也每完全了解）我们就先把他看作一个平常的字典。然后创建键值对，将nums数组的数据按
{键=整数：值=序号}
的形式创建哈希表
如图
顺便提一下enumerate()的功能，获取每个元素的索引及其值
nums = [4, 5, 2, 1]for i, number in enumerate(nums): print(i, number)---------------------输出：0 4
1 5
2 2
3 1
第一列为序号，第二列为值
现在我们来看完整过程
ef findChild(nums, mom): Hash_table = dict() # 创建哈希表 for i, item in enumerate(nums): if mom - item in Hash_table: print([Hash_table[mom - num], i]) # 满足条件输出序号列表 hashtable[nums[i]] = i # 不满足条件继续创建哈希列表接下来我们回到mom - child1的问题。
由题mom = child1+child2，----> mom - child1 = child2
所以我们从找两娃变成了找一娃，简化了过程
举例说明
(item,相当于child1）
nums = [4, 5, 2, 1] mom = 7
1.mom - item = 7 - 4 = 3, 3不在Hash_table
2. hashtable[nums[i]] = i,将4 0，加入Hash_table,----{4:0}
再循环
1.mom - item = 7 - 5 = 2, 2在Hash_table，满足if条件
2. 输出[mom - item在Hash_tabl对应的值，i]--------->[2在Hash_tabl对应的值,i]
--------->[3, 1]
3对应2， 1对应5， 2+5=7 得到结果
这时一些步骤分解过程，还不太清楚的可以看一下
好了，青蛙找到娃了
-----------------------------end--------------------------