python - 在列表中找到四个数字加起来等于目标值

Question

下面是我为解决这个问题而编写的代码:在一个列表中找到四个加起来为 x 的数字。

def sum_of_four(mylist, x):
    twoSum = {i+j:[i,j] for i in mylist for j in mylist}
    four = [twoSum[i]+twoSum[x-i] for i in twoSum if x-i in twoSum]
    print four
sum_of_four([2, 4, 1, 1, 4, 6, 3, 8], 8)

我得到的示例输入答案是:

[[1, 1, 3, 3], [1, 2, 3, 2], [3, 1, 3, 1], [3, 2, 1, 2], [3, 3, 1, 1]]

但是，这个列表列表包含重复项。例如，[1,1,3,3] 与 [3,3,1,1] 相同。

如何打印没有重复列表的列表列表？我想在运行时和空间上尽可能高效。是否可以更改我的列表理解，以便我不打印重复项？我当然不想对列表进行排序，然后使用 set() 删除重复项。我想做得更好。

Answer 1

正确且相对有效的方法是从计算每个值在输入列表中出现的次数开始。假设 value 出现 count 次。然后，您可以将最多 count 个 value 副本附加到一个列表中，您可以在该列表中构建一系列值。在附加 value 的任何副本之前，以及在附加每个副本之后，进行递归调用以移动到下一个值。

我们可以按如下方式实现此方法:

length = 4

# Requires that frequencies be a list of (value, count) sorted by value.
def doit(frequencies, index, selection, sum, target, selections):
  if index == len(frequencies):
    return
  doit(frequencies, index + 1, selection[:], sum, target, selections)  # Skip this value.
  value, count = frequencies[index]
  for i in range(count):
    selection.append(value)
    sum += value
    if sum > target:
      return  # Quit early because all remaining values can only be bigger.
    if len(selection) == length:
      if sum == target:
        selections.append(selection)
      return  # Quit because the selection can only get longer.
    doit(frequencies, index + 1, selection[:], sum, target, selections)  # Use these values.

def sum_of_length(values, target):
  frequency = {}
  for value in values:
    frequency[value] = frequency.setdefault(value, 0) + 1
  frequencies = sorted(frequency.items())  # Sorting allows for a more efficient search.
  print('frequencies:', frequencies)
  selections = []
  doit(frequencies, 0, [], 0, target, selections)
  return list(reversed(selections))

print(sum_of_length([2, 4, 1, 1, 4, 6, 3, 8], 8))
print(sum_of_length([1, 1, 1, 2, 2, 3, 3, 4], 8))
print(sum_of_length([-1, -1, 0, 0, 1, 1, 2, 2, 3, 4], 3))

顺便说一下，您的示例输入的正确答案是 [[1, 1, 2, 4]]。只有一种方法可以从 [2, 4, 1, 1, 4, 6, 3, 8] 中选择四个元素，使得它们的和为 8。