python - 有人可以解释这个 if 语句是如何工作的吗？

Question

有人可以解释一下 if 语句是如何工作的或者下面代码中代码的含义吗？

我有两个列表，A 和 B，我需要查看是否存在一对元素，一个来自 A，另一个来自 B，这样交换它们将使两个列表的总和相等。

我的方法 O(n^2) 是找到 sumOfA 和 sumOfB。 找到 halfdiff = (sumOfA - sumOfB)/2 对于 A 中的每个元素，查看是否存在 B[i] 以便 (A[j] - B[i]) = halfdiff。

但下面的代码在 O(n+m) 中完成。而且我不明白这里“if”语句(第 11 行)的含义。如果它是真的，它是否保证我们有所需的对？

1  def fast_solution(A, B, m):
2    n = len(A)
3    sum_a = sum(A)
4    sum_b = sum(B)
5    d = sum_b - sum_a
6    if d % 2 == 1:
7      return False
8    d //= 2
9    count = counting(A, m)
10   for i in xrange(n):
11     if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
12       return True
13   return False

Answer 1

你必须找到i , j这样 sum(A) - a[i] + b[j] = sum(B) - b[j] + a[i] ，或等效地，sum(A) - 2*a[i] = sum(B) - 2*b[j] .

您可以通过计算右侧的所有可能结果，然后搜索可能的 i 值来完成此操作。

def exists_swap(A, B):
    sumA = sum(A)
    sumB = sum(B)
    bVals = set(sumB - 2 * bj for bj in B)
    return any(sumA - 2 * ai in bVals for ai in A)

除了d = (sum(B)-sum(A))/2，您问题中的部分代码也在做类似的事情。和 count是itertools.Counter(A) (也就是说，它是一个将任何 x 映射到它在 A 中出现的次数的字典)。那么count[B[i] - d] > 0相当于有一个j这样 B[i] - d = A[j] , 或 B[i] - A[j] = (sum(B) - sum(A))/2 .

可能不是使用集合或字典，而是值 m是 A 中允许的最大值和 B .那么counting可以这样定义:

def counting(xs, m):
    r = [0] * (m+1)
    for x in xs:
        r[x] += 1
    return r

这是表示一组整数的一种简单但效率低下的方法，但它可以理解您问题的缺失部分并解释边界检查 0 <= B[i] - d and B[i] - d <= m如果你使用 set 或 dict，这是不必要的，但如果 counting 是必需的返回一个数组。