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。把第二个数组放进哈希集合即可把枚举一对数降成枚举一个数。
解法：代数化简 + 哈希集合
核心思路
先用宽整数求两边总和，避免长数组求和溢出。令
half = (S1-S2)/2。不变量是：扫描到
array1的元素 a 时，只有b = a-half能让交换后的和相等。哈希集合回答这个唯一候选是否真实存在于第二个数组；存在就立即返回。奇数差不可能被两倍的整数差表示，直接无解。Java 中候选 b 也先保留为
long，确认落在 int 范围后再查集合，避免窄化溢出碰巧命中错误值。例：
array1=[4,1,2,1,1,2]，和为 11；array2=[3,6,3,3]，和为 15。half=-2，扫描到 a=4 时需要 b=6，集合中存在。交换后两边都变成 13，返回[4,6]。
解题步骤
- 扫描两个数组求
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, 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 := 0, 0
s := map[int]bool{}
for _, a := range array1 {
s1 += a
}
for _, b := range array2 {
s2 += b
s[b] = true
}
diff := s1 - s2
if (diff & 1) == 1 {
return []int{}
}
diff >>= 1
for _, a := range array1 {
if b := a - diff; s[b] {
return []int{a, b}
}
}
return []int{}
}
复杂度分析
- 时间复杂度：期望
O(n+m)，分别扫描两个数组，哈希查询均摊O(1)。- 空间复杂度：
O(m)，集合最多保存第二个数组的 m 个不同值。
关键点总结
- 先写交换后的等式再移项，符号自然得到
a-b=(S1-S2)/2，比凭感觉猜差值稳。- 奇偶性是零成本剪枝：总和差为奇数时整数交换不可能补平。
- 总和与中间差使用宽整数，数组元素是 int 不代表总和也安全。
- 面试追问若两个数组已排序，可以用双指针寻找固定差值，把额外空间降到
O(1)；未排序时哈希方案更直接且不修改输入。
易错点总结
- 错误写法：把差值符号写反，令
b = a + half。反例中half = -2，会查找b = 2并返回错误交换；正确候选是 6。- 不判奇偶直接整数除法：
S1-S2=3时除 2 截断成 1，可能返回一对交换后仍相差 1 的数。- 用 int 累加总和：元素多且值大时溢出，diff 的奇偶和候选都会被破坏。
- Java 把 long 候选直接强转 int：超范围值回绕后可能碰巧存在于集合，返回一个并不能平衡总和的假答案。
- 集合建在 array1 却仍按当前公式枚举 array1：查询的是同一侧，无法保证 b 来自 array2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 固定补数 + 哈希查找 |
| 888. 公平的糖果交换 | 简单 | 完全相同的总和差代数 |