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解决方案是可接受的，因为它们都是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解决方案很好，但您的代码也可以完成这项工作。

Answer 2

这段代码在面试中是可以接受的，但在现实生活中，你应该学习了解这些库。在本例中，它是itertools.combinations

from itertools import combinations

for item in combinations([2, 8, 7, 15], 2):
    if sum(item) == 9:
        print item  # prints (2, 7)

Answer 3

暴力(朴素)，时间复杂度O(n^2):

class Solution:
    def twoSum(self, nums, target):
        for i in range(0, len(nums)):
            to_find = target-nums[i]
            for j in range(0, len(nums)):
                if j!=i and nums[j] == to_find: 
                    return [i, j]
        return [-1, -1]

使用排序的，时间复杂度O(nlogn):

class Solution:
    def twoSum(self, nums, target):
        nums = sorted(nums)
        for i in range(len(nums)):
            to_find = target - nums[i]
            left, ryt = 0, len(nums)-1
            while left<ryt:
                mid = (left+ryt)//2
                if mid != i and nums[mid] == to_find:
                    return [i, mid]
                elif nums[mid]>to_find:
                    ryt = mid-1
                else:
                    left = mid+1
        return [-1, -1]

使用双指针排序方法的，时间复杂度为O(nlogn):

• 改进了上述排序方法，但时间复杂度仍为O(nlogn)

使用哈希图的，时间复杂度O(n):

class Solution:
    def twoSum(self, nums, target):
        num_to_idx = {}

        for i, num in enumerate(nums):
            if target-num in num_to_idx:
                return [i, num_to_idx[target-num]]
            num_to_idx[num] = i
        return [-1, -1]