写在前面
-
难度：简单
-
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的思路
1. 遍历列表，因为返回的是元素的索引就可以通过enumerate来记录
2. 找到第一个元素，就去找这个元素与目标的差，如果在（余下的列表中）就返回2个元素的索引
3. 依次循环做到最后第二个即可（但其实这个无需你处理）
但是要注意几点
1. 这个数不能用两遍，意味着只能在排除了当前数，（往后面）余下的列表中去找
2. 返回的是2的数的索引，还是在余下的表中找出来的索引，但要加上自己之前的索引信息
3. 默认是一定是能找到的，不用考虑找不到的情况
我的代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i,v in enumerate(nums): #思路1.
if target-v in nums[i+1:]: #思路2.
return [i,nums[i+1:].index(target-v)+i+1] #注意2.
-
分析
由于主要用的是list，耗时和内存比较大，可以考虑用字典
参考代码：用字典的思路1
1. 将nums中的索引和值构造成一个字典
2. 遍历列表，如果target-v的差值在字典中，且索引号不同就返回
注意点：
1. 为何是索引号不同就返回呢，如果索引号相同的话，就是同一个数，那对于偶数target，如果target/2在里面只有一个就有问题了。
2. 由于要对索引号进行比较，一般用key来取value，那么我们应该把nums中的index作为value，列表中元素的值是key
3. 基于2，列表中的值做key的话，可能会重复，导致后面的覆盖前面的，但是我们要明白，如果重复的值是结果的话，我们要得到的就是2个数据的索引，第一个值应该在nums中，第二个值在构造的字典中，是没有问题的。
class Solution:
def twoSum(self, nums: list, target: int) -> list:
dict_nums = { v:i for i,v in enumerate(nums)}
for i,v in enumerate(nums):
if target-v in dict_nums and dict_nums[target-v]!=i:
return [i,dict_nums[target-v]]
参考代码：用字典的思路2
字典其实可以不先构造好。
可以遍历列表，如果当前数与target的差在字典中，就返回当前值的索引和字典中已有数据对应的value，否则就放入字典中待用。
class Solution:
def twoSum(self, nums: list, target: int) -> list:
dict_nums ={}
for i,v in enumerate(nums):
if target-v in dict_nums:
return [dict_nums[target-v],i]
else:
dict_nums[v]=i
-
最佳内存分配
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1,len(nums)): if nums[i]+nums[j]==target: return [i,j]-
分析
看了下内存最好的处理方案，两次循环，但时间消耗应该是大的。
-
-
官方解释
-
暴力法（最佳内存分配）
时间复杂度：O(n^2) 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2) 空间复杂度：O(1)
-
用字典的思路1
时间复杂度：O(n) 我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n) 空间复杂度：O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。
-
用字典的思路2
时间复杂度：O(n) 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。 空间复杂度：O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素