arrays - 给定两个数组 A 和 B ，找到两个数组中的第一个数字，使得替换它们使得数组 A 的总和等于数组 B 的总和

Question

让我们考虑一下

A = [1,7,9,10] sumA = 27
B = [0,10,9,6] sumB = 25

从 A 和 B 中找到第一个元素(如果存在)，如果我们用 B[j] 替换 A[i]。总和=总和

在这里，如果我们用 0 替换 1。

sumA=sumB=26

我知道 O(n2) 的蛮力解决方案。但是需要一个更好的解决方案，例如 O(n)。

谢谢。

Answer 1

是的，有一个O(n) 的解决方案涉及对其中一个数组的值进行哈希处理；因为对于数组 A 中的每个元素 a，数组 B 中只有一个可能的元素 b这将解决问题:

sumA - a + b = sumB - b + a

2*b = sumB - sumA + 2*a

b = (sumB - sumA) / 2 + a

在 O(n) 中散列 B 的值，在 A 中散列每个元素 a ，在 O(1) 中确定值 (sumB - sumA)/2 + a 是否存在于 B 中。