在 A 和 B 之间交换元素以获得总和相等

Question

我们有两个等长的数组，A和B。此外，对于每个i：0 <= a_i, b_i <= m对于某些1<=m<= 1000000。我们想检查某个 term ofA和某个 term of之间的单个交换B是否会使数组的总和相等。

考虑以下解决方案：

def fast_solution(A, B, m):
  n = len(A)
  sum_a = sum(A)
  sum_b = sum(B)
  d = sum_b - sum_a
  if d % 2 == 1:
    return False
  d //= 2
  count = counting(A, m) # returns a mapping <integer, #occurrences in A>
  for i in range(n):
    if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
      return True
  return False

如果你能解释最后一个if条款背后的推理，我会很高兴。

问题的根源

Answer 1

如果存在这样的交换，那么两个值之间的差值必须是总和差值的一半。交换两个值意味着两个列表的总和将发生变化，一个上升，另一个下降，变化幅度相同。两次变化的总和必须等于交换前总和之间的差值，并且两个总和的变化值相同（+d和-d，或值delta，这是两个交换值之间的差值）。

首先，该函数计算d总和之间的差值，即和差值。请注意，sum_a可能是更大的比sum_b，在这一点的结果sum_b - sum_a是否定的。这只是意味着必须有一个B小于目标值的值A，然后交换会减少sum_a和增加sum_b以使它们相等。如果和 delta 的奇偶校验是奇数而不是偶数，您将永远找不到一个值 delta 是和 delta 的一半，因此函数此时返回False。的最终值d是值delta，即两个交换值之间的差异量。请记住，值 delta 是总和 delta 的一半。

该算法计算 中的所有值A，然后测试 中的所有值B。这将只可能之间交换两个值A并且B如果有一个在值B由不同d从一个价值A。A要交换的值B需要等于b_value - d。对于负数d( sum_a > sum_b) 会变b_value小，对于正数则d需要b_value更大的数字。

该if测试查看 中是否有B - d可用值A，但它首先测试是否b_value - d仍在 [0-m] 的范围内：

• 0 <= B[i] - d 测试在 A 中寻找的数字是否仍然是正数。
• B[i] - d <= m测试所寻求的数字是否仍然不大于m; 如果B[i]接近并且d是负数，则可能是。
• count包含 中数字的计数A；如果count[B[i] - d] > 0为真，则 A 中至少有一个这样的数字。这是一个可以交换的数字。

需要范围测试是因为该counted列表仅包含从 0 到 m（含）的数字的计数，而不包含负数或大于 的数字的计数m。

可以通过使用集合代替计数功能来改进该功能。不需要知道一个数字出现了多少次A，只要知道它存在即可。这将使边界检查过时，因为超出范围的数字根本不会出现在 的一组值中A。

一旦我们有了一组 A 值，我们就可以使用以下方法测试该集合是否与应用了 delta 的 b 值集合不相交set.isdisjoint()：

def faster_solution(A, B, m=None):  # m is ignored in this version
    delta = sum(A) - sum(B)
    if delta % 2 == 1:
        return False
    delta //= 2
    return not set(A).isdisjoint(b - delta for b in B)

返回true，如果有一个值A等于一个价值B减去三角洲。Python 只会在循环上b - delta for b in B循环直到找到匹配（此时集合不会不相交，并且not结果为 True），或者循环已用完，因此在其中找不到这样的值A并且集合被找到不相交。

显示的counter()函数还有另一个问题：它需要的内存比实际需要的多，并且与具有优化循环以进行计数的collections.Counter()对象相比，它非常慢。ACounter()使用字典（散列图）仅存储大于 0 的计数。

上面的固定解决方案击败了“快速解决方案”：

>>> import timeit, random
>>> m = 1000000
>>> testdata = [random.randrange(m + 1) for _ in range(1000)]
>>> testinputs = (testdata[:], testdata[:])
>>> random.shuffle(testinputs[0])  # The order of A differs from B
>>> testinputs[1][-1] -= testinputs[1][-1] // 2  # now the two sums differ by an even amount, guaranteed to be in range
>>> assert testinputs[1][-1] > 0  # make sure the original random value was not 0 or 1.
>>> # note: It's the *last value in B* that makes it possible to swap;
... # this is one of two worst-case scenarios (the other is even-delta-no-swap).
...
>>> assert fast_solution(*testinputs, m)    # the original finds a solution
>>> assert faster_solution(*testinputs, m)  # my version finds a solution
>>> timeit.timeit("f(*ab, m)", "from __main__ import fast_solution as f, testinputs as ab, m", number=1000)
2.3270092820748687
>>> timeit.timeit("f(*ab, m)", "from __main__ import faster_solution as f, testinputs as ab, m", number=1000)
0.13949943508487195

不使用计数器，而使用 Python 的 set 功能可以使长度为 1000 的输入快 17 倍！

这个故事的寓意是：使用您选择的语言中可用的最佳工具，并批判性地思考解决问题的实际需要。Python 的内置类型和操作通常可以让您避免在 Python 字节码中运行关键循环，从而显着减少算法的常量时间因素。

Answer 2

来自https://www.geeksforgeeks.org/find-a-pair-swapping-which-makes-sum-of-two-arrays-same：

我们正在寻找两个值，a 和 b，这样：

sumA - a + b = sumB - b + a
2b - 2a = sumB - sumA
b - a = (sumB - sumA) / 2

(sumB - sumA) / 2是目标差异d

count[B[i] - d] > 0- 这仅仅意味着数组中必须存在这样的值A才能满足条件