Codility Counting Lesson

Question

我正在学习Codility Counting Lesson(https://codility.com/media/train/2-CountingElements.pdf),我需要帮助才能理解最快的解决方案.

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

问题:

您将得到一个整数m(1 < m < 1000000)和两个非空,零索引的数组A和B的n整数a0,a1,..., an?1和b0,b1...,bn?1分别为(0 < ai,bi < m).目标是检查是否存在可以在这些数组上执行的交换操作,使得数组中的元素A总和等于B交换后数组中元素的总和.通过交换操作,我们的意思是,从采摘数组一个元素A的数组一个元素,并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)
   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 for Python 2,或https://docs.python.org/3/library/collections.html#collections.Counter for Python 3.