python - LeetCode Python TwoSums

Question

我对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 算法答案应该是什么样的？这个可以面试吗？谢谢

Answer 1

我认为您的代码或 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 解决方案很好，但您的代码也能完成工作。