python - Codility计数课

Question

我正在学习 Codility 计数课 ( https://codility.com/media/train/2-CountingElements.pdf )，我需要帮助来了解最快的解决方案。

我想知道为什么第 8 行中差值除以 2 d //= 2 ？差异是否足以找到我们可以在数组之间交换的元素？

问题:

You are given an integer m (1 < m < 1000000) and two non-empty, zero-indexed arrays A and B of n integers, a0, a1, ... , an−1 and b0, b1, ... , bn−1 respectively (0 < ai, bi < m). The goal is to check whether there is a swap operation which can be performed on these arrays in such a way that the sum of elements in array A equals the sum of elements in array B after the swap. By swap operation we mean picking one element from array A and one element from array B and exchanging them.

解决方法:

 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)
   for i in xrange(n):
       if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
           return True
   return False

Answer 1

A[i] 和 B[j] 之间的交换将 B[j]-A[i] 添加到 sum(A) 和从sum(B) 中减去相同的值；因此它影响总和的差 两倍 B[j]-A[i]。

因此，将原始差异减半(在检查它是偶数之后——如果它是奇数，则没有交换将起作用!-)以形成可能交换的目标是正确的。

另请注意，它们提供的 counting 函数并不是现代 Python 的最佳选择——为避免重新发明“计数项目”的特定轮子，请参阅 https://docs.python.org/2/library/collections.html#collections.Counter对于 Python 2，或 https://docs.python.org/3/library/collections.html#collections.Counter适用于 Python 3。