LeetCode 面试题 16.21. 交换和
题目描述
题意分析
从
array1选一个数 a、从array2选一个数 b 交换，使交换后两个数组元素和相等；找到任意一组即可，无解返回空数组。朴素做法枚举所有
(a,b)，每对再验证，时间是O(nm)。真正有用的信息只有两边总和。设原和为S1、S2，交换后满足S1-a+b = S2-b+a，整理得到：
a - b = (S1 - S2) / 2。因此总和差必须是偶数；一旦固定 a，所需的 b 唯一等于
a - (S1-S2)/2。把第二个数组放进哈希集合即可把枚举一对数降成枚举一个数。
解法：代数化简 + 哈希集合
核心思路
[!blue]
先用 64 位整数求两边总和与差
diff = S1 - S2。交换a、b会让第一边减少a - b、第二边增加同样的量，因此原总和差必须等于2 * (a - b)。差为奇数就不可能通过整数交换消除；这个判断也适用于负差值。差为偶数时，令
half = diff / 2，代码直接复用diff保存这个值。固定第一个数组中的a后，唯一可能的交换对象是b = a - half。把第二个数组的元素加入哈希集合，就能快速判断这个对象是否真实存在，无需再枚举第二个数组的所有位置。枚举每个
a不会漏解：任何合法交换都满足推导出的等式，所以一定会在对应的a处查到b；反过来，找到集合中的b就能直接代回等式，使两边总和相等。只交换一个元素，因此第二个数组中的重复值只需保留“是否存在”，不需要计数。候选值的运算也使用 64 位。Java 集合存放
int，只有候选落在其范围内才能转换并查找，避免窄化后误命中；Go 集合直接保存int64，命中后才转回原元素类型。若两边原总和相等，仍需找到公共值完成一次等值交换，不能直接认定存在可返回的数对。
解题步骤
- 扫描两个数组求
S1、S2，同时把array2的值加入集合。- 计算
diff=S1-S2；若 diff 为奇数，返回空数组。- 令
half=diff/2。- 枚举 array1 的 a，计算唯一候选
b=a-half。- b 在整数范围内且存在于集合时返回
[a,b]；扫描结束仍未命中则无解。
代码实现
class Solution {
public int[] findSwapValues(int[] array1, int[] array2) {
long s1 = 0;
long s2 = 0;
Set<Integer> s = new HashSet<>();
for (int x : array1) {
s1 += x;
}
for (int x : array2) {
s2 += x;
s.add(x);
}
long diff = s1 - s2;
if (diff % 2 != 0) {
return new int[0];
}
diff /= 2;
for (int a : array1) {
long candidate = (long) a - diff;
if (candidate >= Integer.MIN_VALUE
&& candidate <= Integer.MAX_VALUE
&& s.contains((int) candidate)) {
return new int[] {
a,
(int) candidate
};
}
}
return new int[0];
}
}
func findSwapValues(array1 []int, array2 []int) []int {
s1, s2 := int64(0), int64(0)
s := map[int64]bool{}
for _, a := range array1 {
s1 += int64(a)
}
for _, b := range array2 {
s2 += int64(b)
s[int64(b)] = true
}
diff := s1 - s2
if (diff & 1) == 1 {
return []int{}
}
diff >>= 1
for _, a := range array1 {
if b := int64(a) - diff; s[b] {
return []int{
a,
int(b),
}
}
}
return []int{}
}
复杂度分析
- 时间复杂度：期望
O(n+m)，分别扫描两个数组，哈希查询均摊O(1)。- 空间复杂度：
O(m)，集合最多保存第二个数组的 m 个不同值。
关键点总结
[!green]
- 先写交换后的等式再移项，符号自然得到
a-b=(S1-S2)/2，比凭感觉猜差值稳。- 奇偶性是零成本剪枝：总和差为奇数时整数交换不可能补平。
- 总和与中间差使用宽整数，数组元素是 int 不代表总和也安全。
- 每个候选都同时满足差值等式与跨数组存在条件，返回后即可执行实际交换。
易错点总结
[!yellow]
- 固定 a 后需要 b=a-half，不能把符号写反。
- 总和差为奇数时无解，不能直接整数除二后继续匹配。
- 两边总和及差值使用 64 位；溢出会改变需要查找的候选值。
- Java 集合存 int，候选 long 需检查范围再转换；Go 集合直接存 int64，只有命中已存在的原元素时才转换返回。
- 集合必须来自另一数组，才能保证实际执行跨数组交换。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 888. 公平的糖果交换 | 简单 | 同样由交换前后总和相等推导差值，原题是糖果数量，本题支持一般整数数组。 |
| 1. 两数之和 | 简单 | 同样固定一个元素后查询唯一互补值，本题补数由两数组总和差决定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！