-1

我想在 python3 中使用“枚举”来解决以下任务

枚举的工作方式如下所示

nums=(2,7,1,15)               # a tuple  

for num in enumerate(nums):
        print(num, 'hello')   

#output
#(0, 2) hello        #enumarate(nums) = (0,2)
#(1, 7) hello
#(2, 1) hello
#(3, 15) hello      


for count, num in enumerate(nums):
        print(num, 'hello')      

# Output
#2 hello    here count=0 but not displayed 
#7 hello    here count=1 but not displayed
#1 hello    here count=2 but not displayed
#15 hello   here count=3 but not displayed

使用上述原理，给定一个由 n 个整数组成的数组 nums，在 nums 中是否存在元素 a、b、c 使得 a + b + c = 目标总和？在数组中找到所有唯一的三元组，其总和 = 目标总和。

目标总和 =10 的解集是：

[
  [0,1,2]             
]

其中第 0 个索引处的 num+第 1 个索引处的 num+第 2 个索引处的 num (7+2+1=10)。

4

2 回答 2

2

你有解决问题的算法的想法吗？

我可能会做一些事情，比如建立两个dicts 列出使用数组索引的所有方法，用 1 个数字和 2 个数字求和作为某个键值。

例如，如果我得到了nums = [2, 7, 1, 2, 3]，我会编写代码来建立一个表格，例如：

one_sum = {1: [2], 
           2: [0, 3], 
           3: [4],
           7: [1]}

我将使用defaultdictfrom collections 模块来有效地编写此代码（one_sum = defaultdict(list)如上所述初始化，尽管 aset也是该问题的有效数据结构）。

这部分使用起来很简单enumerate；例如，

for i, n in enumerate(nums):
    one_sum[n].append(i)

然后，我将建立一个two_sum表格，显示所有具有一定总和的索引对。继续上面的示例，我想生成：

two_sum = {3: [(0, 2), (2, 3)],
           4: [(2, 4)],
           5: [(0, 4), (3, 4)],
           8: [(1, 2)],
           9: [(0, 1), (1, 3)],
          10: [(1, 4)]}

（注意一种有效的方法是循环遍历建立的one_sum，但注意不要重复使用索引，例如，不要添加(2,2)或(4,4)因为two_sum[4]whilenums[2] + nums[2]加起来是 4，它使用索引两次（所以是'不是唯一的）。还要注意不要重复添加无序的索引。）

最后，我将遍历one_sum字典，查看总和为的索引，k然后two_sum查看是否有任何总和为的索引对，如果有target-k，则将这些对连接在一起（检查对索引进行排序，而不是在 a tuple) 找到了解决方案。

对于 10 的目标，这将在理想情况下建立

three_sum = [(0,1,2), (1,2,3)]

# Note both were added from combining one_sum[1] with two_sum[9]
# nothing from combining one_sum[2] with two_sum[8] as they reuse indexes
# nothing from combining one_sum[3] as two_sum[7]==[]
# nothing new from combining one_sum[7] with two_sum[3] as (0,1,2) and (1,2,3) already present.
于 2018-06-09T04:36:49.707 回答
0

这是一种蛮力方法。请注意，它的效率不如该算法。

def f(nums, target):
    sols = []
    for i1, n1 in enumerate(nums):
        for i2, n2 in enumerate(nums[i1+1:]):
            for i3, n3 in enumerate(nums[i2+1:]):
                if (n1 + n2 + n3 == target):
                    sols.append([i1, i2, i3])
    return sols
于 2018-06-09T04:05:27.927 回答