时间戳

首页 > 解决方案 > 从 4 个给定的数组（未排序）中，从每个数组中找到总和等于某个数字 X 的元素

python - 从 4 个给定的数组（未排序）中，从每个数组中找到总和等于某个数字 X 的元素

问题描述

假设有 4 个未排序的数组，如下所示：

A = [0, 100, -100, 50, 200]
B = [30, 100, 20, 0]
C = [0, 20, -1, 80]
D = [50, 0, -200, 1]

假设 X 为 0，那么可能的 O/P 中的少数应该是（从每个数组中选择 1 个满足条件的元素）：

0,0,0,0
-100, 100, 0, 0
-100, 30, 20,50 .. etc.

我能够设计出可以在 O(n^3LogN) 中做到这一点的算法，有没有更好的方法来实现这一点？

我的解决方案：

1-对每个数组进行排序。

2- 修复了数组 A 中的元素。

3-对其余数组运行三个循环并取每个元素的总和：

if sum > 0 (return -1, no such elements exit)

if sum == 0 (return current elements)

if sum < 0 (then advance the pointer from the array for which the current element is minimum.)

对此有何建议？

标签： pythonalgorithm

解决方案

假设您的数组都具有相同的长度n（+/- 一些常数值），您可以O(n^3)通过使用 aset来获得第四个数组：

from itertools import product

ds = set(D)
for a, b, c in product(A, B, C):
    d = X - a - b - c
    if d in ds:
        print(a, b, c, d)

如果一个或多个数组包含（许多）极值，您还可以通过检查后续数组的运行总和来查看是否min仍然可以达到。例如：maxX

ds = set(D)
c_min, c_max = min(C), max(C)
d_min, d_max = min(ds), max(ds)
for a in A:
    for b in B:
        s = a + b
        if s + c_min + d_min > X or s + c_max + d_max < X:
            continue  # Shortcut here.
        for c in C:
            d = X - a - b - c
            if d in ds:
                print(a, b, c, d)

您可以通过存储已经为运行总和（例如前两个数组）找到的解决方案来进一步扩展它，因此每当再次遇到这样的总和时都会采取捷径（通过使用最小/最大检查重新排序可以避免重复计算 s + 最小值/最大值）：

ds = set(D)
c_min, c_max = min(C), max(C)
d_min, d_max = min(ds), max(ds)
shortcuts = {}
for a in A:
    for b in B:
        s = a + b
        if s in shortcuts:
            for c, d in shortcuts[s]:
                print(a, b, c, d)
            continue
        shortcuts[s] = []
        if s + c_min + d_min > X or s + c_max + d_max < X:
            continue
        for c in C:
            d = X - a - b - c
            if d in ds:
                print(a, b, c, d)
                shortcuts[s].append((c, d))

推荐阅读