题目描述:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解法一:穷举法暴力解题
思路:根据nums中的索引,用穷举法将所有不同的两个数相加,当和为target,则返回这两个数的索引值,即为我们所需要的数组下标。若找不到两个数的和为target,则返回一空列表。
时间复杂度:O(n^2)
代码:
解法二:哈希表法
哈希表,是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
通过enumerate()建立一个字典,模仿哈希表,在建立字典的同时,查找字典中是否有与target-num相对应的键,如果字典中存在,则返回num与target-bum两个数的索引。
时间复杂度:O(n)