作为一个半路出家的算法小白，最近尝试着刷一下力扣，来扩展些思维，毕竟总是写一些复杂度非常高的代码也不是那么回事。
当然作为一个绝对有自知之明的人，这种时候一定是从最简单的算法题开始，先看看自己的斤两再说吧。
我这里还为自己立下了一个小目标，就是每道算法题，都会尝试用 Python 和 Java 两种语言来求解，并且会顺带这分析算法题背后的知识点，毕竟解题是一方面，背后的知识还是要弄清楚的，希望自己能够坚持下去。
两数之和
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
先来看看最为暴力的两层循环解法
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)-1): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j]
其实这种解法不用说太多，无非就是循环两次列表，如果在内循环中找到 target 值，则返回对应的索引。
那么来看看这种简单粗暴的方法成绩怎么样呢
执行时间真的是惨不忍睹啊，这个击败比率都快赶上我的电脑开机速度的战斗值了。
优化一
我们可以把给定的列表进行排序，然后通过比较首尾两数之和与 target 之间的大小来判定目标索引的位置，这种方法只需要进行一次排序就可以实现。
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: sorted_id = [k for k,v in sorted(enumerate(nums), key=lambda k: k[1])] head = 0 tail = len(nums) - 1 sum = nums[sorted_id[head]] + nums[sorted_id[tail]] while sum != target: if sum > target: tail -= 1 else: head += 1 sum = nums[sorted_id[head]] + nums[sorted_id[tail]] return [sorted_id[head], sorted_id[tail]]
如果当前两数之和大于 target，则移动尾部索引；反之则移动首部索引。
这种方法的关键就是获取到排序后原列表的元素索引，对应的代码为
sorted_id = [k for k,v in sorted(enumerate(nums), key=lambda k: k[1])]
这句话比较绕，我们来具体看下：
比如有列表 l = [1, 3, 2, 4]，那么通过上述代码后，会得到列表 sorted_id = [0, 2, 1, 3]，即实际上我们可以隐性的知道排序后的列表为 [1, 2, 3, 4] 即 [sorted_id[0], sorted_id[1], sorted_id[2], sorted_id[3]]。
关键函数说明：
enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标。
>>> l = [1, 3, 2, 4] >>> list(enumerate(l)) [(0, 1), (1, 3), (2, 2), (3, 4)] >>>
当然，这里还有一种更为简单的排序方法
sorted_id = sorted(range(len(nums)), key=lambda k: nums[k])
以上两段排序代码都是我们在该算法题中可以额外学习到的技能。
优化二
第二种优化方式为利用 Python 的字典，来保存列表数值与对应的索引。
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: map = {} for index, num in enumerate(nums): gap_num = target - num if gap_num in map: return [map[gap_num], index] map[num] = index return None
可以看到，还是通过函数 enumerate 获取列表的数值与索引，然后依次放置字典中，先进行 if 判断，如果存在则直接返回中止程序。
其实 Python 中的字典就是一种哈希表，那么它与 Java 中的 HashMap 有什么区别呢？
其实 Python 中的字典也是哈希表的一种，与 Java 语言中的 HashMap 是同一种数据结构，所不同的是字典在遇到哈希冲突时，采用开放寻址法，而 HashMap 采用的是链表法。
我们先来看下什么是哈希表：
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
记录的存储位置=f(关键字)，这里的对应关系f称为散列函数，又称为哈希（Hash函数）。
哈希表 hashtable(key，value) 就是把 Key 通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将 value 存储在以该数字为下标的数组空间里。
那么 Java 中的 HashMap 使用的链表法是什么意思呢，就是说当哈希冲突时，会在数组的对应索引下挂一个链表来存储冲突的值，而 Python 字典的开放寻址法则为当哈希冲突时，通过某些规划把该值存储到其他索引下。
优化三
最后再来看看 Java 语言的解法，最好的办法就是利用 HashMap 来解决该题。
import java.util.HashMap; import java.util.Map; class Solution { public int[] twoSum(int[] nums, int target) { int[] indexs = new int[2]; HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); for(int i = 0; i < nums.length; i++){ if(hash.containsKey(nums[i])){ indexs[0] = i; indexs[1] = hash.get(nums[i]); return indexs; } hash.put(target - nums[i], i); } return indexs; } }
与 Python 的字典解法类似，都是通过依次循环，把对应的数值与索引放入哈希表中然后进行判断。
通过上面的分析可以看出，当我们在试图解决一道问题的时候，我们是可以扩展出很多其他知识的，一起加油吧！
