快速有效地解决二和问题

Question

所以我是竞争性编码的初学者，开始练习Leetcode问题

问题如下:

给定一个整数数组nums和一个整数目标，返回两个数字的索引，使它们相加到目标。 您可以假设每个输入都有一个解决方案，并且不能两次使用同一个元素。 您可以按任意顺序返回答案

例1：

输入：nums=[2,7,11,15]，target=9

输出：[0,1]

输出：因为nums[0]+nums[1]==9，所以我们返回[0，1]

我采用了一种简单的方法，或者你可以称之为蛮力方法：

def twosum(nums,target):
    for i in range(0,len(nums)):
        for j in range(0,len(nums)):
            if i != j and nums[i] + nums[j] == target:
                return i,j

我能做些什么来提高代码的效率和质量

Answer 1

作为一般规则，如果需要索引，请使用enumerate not range（len（..）

def twosum(nums,target):
   for ind1, i in enumerate(nums):
       for ind2, j in enumerate(nums):
           if ind1 != ind2 and i + j == target:
              return ind1, ind2

我想那样会更有效率

我个人会更进一步，使用itertools.product（）

import itertools

def twosum(nums,target):
    for (ind1,i), (ind2,j) in itertools.product(enumerate(num), repeat=2):
            if ind1 != ind2 and i + j == target:
                return ind1, ind2

Answer 2

您可以创建一个dict来存储值及其索引，并通过在dict中减去(target - current_value)进行检查；由于字典查找是固定时间的，因此您可以一次性找到解决方案：

def twosum_O_n(number, target):
    hsh={}
    # Use enumerate to get both current index, and value
    for i, curr_value in enumerate(number):

        # calculate how much it is off target
        other_part = target - curr_value

        # check if that part is in the dictionary
        if other_part in hsh:
            # if it is, return that value, and current_index
            return [hsh[other_part], i]
        else:
            # otherwise store the current index with current value as key
            hsh[curr_value] = i

>>> twosum_O_n([2,7,11,15], target = 9)
[0, 1]

>>> twosum_O_n([0, 5, 11, 4], target=11)
[0, 2]

>>> twosum_O_n([5, 10, -2, 12], target=8)
[1, 2]

一些时间安排：

>>> num = list(range(10000))
>>> target = num[-1] + num[-2]

>>> %timeit twosum(num, target)
12.3 s ± 276 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit twosum_O_n(num, target)
1.44 ms ± 21.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Answer 3

以下是如何做到这一点：

• 步骤1：从左到右遍历列表
• 步骤2：检查列表中的值是否小于或等于9。如果 大于9，忽略该元素。任何大于9的数字 添加不会给我们期望的结果。如果您希望列表中出现负数，请跳过“小于或等于9”复选框
• 步骤3：如果数字小于或等于9，则检查 差异（9-数字）在列表中可用（来自当前 索引+1到列表末尾）。如果答案是肯定的，那么你有一个 匹配
• 步骤4：打印当前索引（第1项）和 数字的余数值为9。第二个的索引将 be：当前索引+1+从中检查时的索引（9-数字） [索引+1:]

这方面的代码是：

nums = [2,7,11,15]
target = 9
for i,n in enumerate(nums):
    if n <= 9 and i < len(nums)-2 and ((9 - n) in nums[i+1:]): 
        print ('Index of the two integers are: ', i, i+1+nums[i+1:].index((9 - n)))
        break
    else:
        print ('No Match')