难度: Medium
给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
示例:
输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3] 输出: [1, 3]
示例:
输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []
提示：
1 <= array1.length, array2.length <= 100000运行时间: 33 ms
内存: 19.9 MB
class Solution:
def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
diff = sum(array1) - sum(array2)
set1, set2 = set(array1), set(array2)
for a in set1:
b = (2 * a - diff) // 2
if 2 * b == 2 * a - diff and b in set2:
return [a, b]
return []
此题目要求从两个数组中各选一个数进行交换，使得交换后两数组的总和相等。首先，我们计算两数组之和的差值 diff = sum(array1) - sum(array2)。如果我们从 array1 中选一个值 a 从 array2 中选一个值 b 进行交换，使得 sum(array1) - a + b = sum(array2) - b + a，这意味着 2a - 2b = diff，即 a - b = diff / 2。因此，对于 array1 中的每个元素 a，我们计算 b = a - diff / 2，然后检查 b 是否存在于 array2 中。为了快速查找，我们可以将 array2 的元素存储在一个集合中。如果找到符合条件的 a 和 b，返回 [a, b]；否则返回一个空数组。
时间复杂度: O(n)
空间复杂度: O(n + m)
class Solution:
def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
# 计算两数组和的差值
diff = sum(array1) - sum(array2)
# 创建两个集合以快速判断元素是否存在
set1, set2 = set(array1), set(array2)
# 遍历第一个数组的集合
for a in set1:
b = (2 * a - diff) // 2
# 检查计算出的 b 是否真实存在于第二个数组中
if 2 * b == 2 * a - diff and b in set2:
return [a, b]
return []
选择使用`b = (2 * a - diff) / 2`这种形式是为了避免出现浮点数运算。在编程语言中，如果`diff`是奇数，除以2会产生小数，这可能导致查找不准确或类型不匹配的错误。通过首先计算`2 * a - diff`，然后除以2，确保了所有的运算都在整数域内进行，从而避免了这种问题。这种方法同时也确保了只在整数解是有效的时候才进行查找，避免了无效的计算和查找。
代码中通过计算`2 * a - diff`并检查结果是否可以被2整除来处理`diff`为奇数的情况。如果`2 * a - diff`是偶数，这意味着`diff`将不会影响`b`的整数性。这种方法确保了即使`diff`为奇数，计算出的`b`也总是整数。这样的处理避免了因`diff`为奇数而导致的非整数`b`值的问题，从而确保`b`总是有效的且可以在数组中查找到。
遍历`set1`与直接遍历`array1`的主要区别在于`set1`是`array1`的去重版本。使用集合来遍历的优点是避免了重复元素的多次检查，提高了算法的效率。然而，这种方法假设每个元素至多只需要交换一次即可达到题目要求。如果`array1`中有重复元素可能多次参与到解中，这种情况下直接遍历`array1`可能会有不同的结果。但对于本题的需求，考虑每个元素一次就足够了，因此使用`set1`可以减少不必要的计算和查找，加快解题速度。