有人能解释一下这个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）中完成的。我不明白这里“如果”语句（第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)（也就是说，它是一个dict，将任何x映射到它在A中出现的次数）。则count[B[i] - d] > 0等价于存在j，使得B[i] - d = A[j]，或B[i] - A[j] = (sum(B) - sum(A))/2。你知道吗

可能不是使用集合或dict，值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返回数组，这是必要的。你知道吗

Answer 2

实际上，它不是O(n+m)。由于hashmapcount的使用，线性估计只是摊销。这些知识可以帮助您理解您的代码是的模糊版本

bool solve(A,B) {
    sum_a = sum(A)
    sum_b = sum(B)
    sort(B)
    for(val in A)
        if( binary_search(B, val - (sum_b - sum_a)/2 ) )
            return true
    return false
}

正如Paul指出的，0 <= B[i] - d and B[i] - d <= m只是对count论证的验证。顺便说一句，他的解决方案是纯线性的，很好地实现和更简单的理解。你知道吗