1.两数之和 Two Sum
题解暴力法复杂度分析PythonJava(待完成)
两次哈希表复杂度分析PythonJava(待完成)
一次哈希表复杂度分析PythonJava(待完成)
题解
暴力法
两次循环 第一次循环，对于数组中每一个数 nums[i] 进行遍历 第二次循环，从当前数的下一个数 nums[j] ,其中 j>i 继续遍历，判断nums[i]+num[j] 是否等于target.
复杂度分析
时间复杂度：
O
(
n
2
)
O\left(n^{2}\right)
O(n2)空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def twoSum(self
, nums
: List
[int], target
: int) -> List
[int]:
n
=len(nums
)
for i
in range(len(nums
)):
for j
in range(i
+1,len(nums
)):
if(nums
[i
]+nums
[j
]==target
):
return [i
,j
]
return False
Java(待完成)
两次哈希表
step1 将数组中所有元素存入词典（哈希表），键为nums[i]，值为索引i.step2 遍历数组，判断target-nums[j] 是否在词典中，且对应的索引不为其本身，即dict[target-nums[j]] 不等于j. 若满足条件，则返回.
复杂度分析
时间复杂度：
O
(
n
)
O\left(n\right)
O(n)空间复杂度：
O
(
n
)
O\left(n\right)
O(n)
Python
class Solution:
def twoSum(self
, nums
: List
[int], target
: int) -> List
[int]:
dict={}
for i
in range(len(nums
)):
dict[nums
[i
]]=i
for j
in range(len(nums
)):
tmp
=target
-nums
[j
]
if(tmp
in dict and dict[tmp
]!=j
):
return [j
,dict[tmp
]]
return False
Java(待完成)
一次哈希表
我们在遍历时，将target-nums[i] 存入词典，值为索引i.这样在遍历时，只要判断后续元素是否存在于词典中，即可满足条件.如：[2,7,11,15] target=9，将9-2=7 存入词典，第二个元素7在词典中存在，则返回.
复杂度分析
时间复杂度：
O
(
n
)
O\left(n\right)
O(n)空间复杂度：
O
(
n
)
O\left(n\right)
O(n)
Python
class Solution:
def twoSum(self
, nums
: List
[int], target
: int) -> List
[int]:
dict={}
for i
in range(len(nums
)):
if(nums
[i
] in dict):
return [i
,dict[nums
[i
]]]
else:
dict[target
-nums
[i
]]=i
return False
Java(待完成)
