我对python绝对是菜鸟,刚开始练习leetcode。不管怎样,看看这个 TwoSum 练习:给定一个整数数组,找到两个数字,使它们加起来等于特定的目标数字。
这是我为这个练习编写的代码:
class Solution(object):
def __init__(self, nums, target):
self.nums = nums
self.target = target
def twoSum(self):
for i in range(len(self.nums)):
for j in range(i+1, len(self.nums)):
if self.nums[i] + self.nums[j] == self.target:
print "index1=" + str(i) + ", index2=" + str(j)
sample = Solution([2, 8, 7, 15], 9)
sample.twoSum()
任何人都可以帮助我 leetcode 算法答案应该是什么样的?这个可以面试吗?谢谢
最佳答案
我认为您的代码或 itertools 解决方案 Not Acceptable ,因为它们都是 O(n^2)
。如果在面试中给出,面试官可能希望看到你可以做得比只运行两个嵌套的 for 循环更好。
我会使用 hash table或者对数组进行排序,然后 binary search答案。
哈希表伪代码
h = empty hash table
for each element e in array
if target - e in hash table:
we have a solution
add e to hash table
这将具有 O(n)
的复杂性,受一些哈希表怪癖的影响:在最坏的情况下,它可能是 O(n^2)
,但是随机输入不应该发生这种情况。
二分查找伪代码
sort array
for each element e in array
binary search for target - e, make sure it's not found at the same index
if it is, check the before / after element
or think how you can avoid this happening
这将始终是 O(n log n)
。
如果复杂性无关紧要,那么 itertools 解决方案很好,但您的代码也能完成工作。
关于python - LeetCode Python TwoSums,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31763724/