题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
链接：两数之和
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
考察知识点：数组，哈希表(字典)
请补充完整如下代码：
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]:
思路
思路：结合题目及提示这里使用字典。
用target减去列表中的某个值，并将该值作为key，其下标作为value存放到字典中，接着target依次减去剩下的列表项中的值并判断结果是否存在于字典，如果存在即表示列表中有两个值相加等于target，此时即可直接返回答案。并且字典存储可以起到去重的作用。
class Solution(): def twoSum(self,nums,target): dict = {} for i,n in enumerate(nums): if target-n in dict: return [dict[target-n],i] else: dict[n] = i if __name__ == "__main__": so = Solution() result = so.twoSum([1,8,9,6,2],10) print(result)
分析总结
大家注意审题，确定输入是什么，输出又是什么，假定又是什么。
输入：待寻找的列表 nums, 两数之和 target
输出：有且仅有满足要求的一对整数的下标
假定：一定存在，且仅有一个答案
题目分析：两个数之和等于 target, 首先标记所有遍历过的数，如果 target 减去当前被遍历到的
值 e 后，即 target-e 被标记过，则找到答案。
判断值是否在某个容器中，做到 O(1) 时间复杂度的便是最常用的散列表，对应 Python 中的字典。就本题而言，键为标记元素值，字典值为数组下标，所以更加确定使用字典这个数据结构。
class Solution: def twoSum(self, nums, target): d = {} for i,e in enumerate(nums): if target-e in d: return [d.get(target-e),i] d[e] = i
不高效解
不高效解 1
index 复杂度为 O(n), 所以实际时间复杂度为 O(n^2)，尽管表面上看只有一个 for 循环。
def twoSum1(nums,target): for index,num in enumerate(nums): another_num = target - num nums[index] = None if another_num in nums: return [index,nums.index(another_num)] return None
不高效解 2
下面代码两层 for，空间复杂度虽然为 O(1)，但是时间复杂度为 O(n^2)。所以需要找到牺牲空间换取时间的方法。
class Solution: def twoSum(self, nums, target): n = len(nums) for i in range(n): for j in range(i+1,n): if nums[j] == target - nums[i]: return i,j break else: continue
以上使用散列表牺牲空间，但是换取时间，实际中能找到节省时间的解往往更有价值。
每日一句
I can because i think i can.(我行，因为我相信我行！)
