算法面试题之两数之和
程序员文章站
2024-03-22 14:13:10
...
两数之和(leetcode 1)
题目:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
解题:
方法一:暴力解法,双重循环
class Solution:
def twoSum(self , numbers , target ):
dic = dict((i,j) for (i,j) in enumerate(numbers))
for i in range(len(dic)):
for j in range(len(dic)):
if dic[i] + dic[j] == target and i != j:
return [i,j]
s = Solution()
print(s.twoSum([0,4,3,0],0))
方法二:用if替换内层循环,减小时间复杂度
# enumerate函数使nums列表变为(索引,值)形式,hashtable是(值:索引)形式的字典
class Solution:
def twoSum(self, nums, target):
hashtable = dict()
for (index,num) in enumerate(nums):
if target-num in hashtable:
return [index,hashtable[target-num]]
hashtable[nums[index]] = index
return []
s = Solution()
print(s.twoSum([0,4,3,0],0))
总结:方法二是面试官希望看到的,方法二中使用if语句判断减少一层循环,时间复杂度由方法一的O(n2)变为O(n).