LeetCode 888. 公平的糖果交换

2026-04-05 HGNULB 约 8 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 888. 公平的糖果交换

题意分析

两个人各有一盒糖果，必须恰好交换一盒，交换之后两人手里糖果总量相等，要求返回任意一组合法的交换方案。注意「必须交换」而不是「可以不交换」，所以即使两人本来总量就相等，也要找出一对大小相同的糖果换过去。

题目保证答案一定存在，这一点非常关键：它意味着不需要处理「找不到解」的返回值，也意味着两人总量之差一定是偶数，除以 2 不会丢精度。

数组长度上限一万量级、糖果大小上限十万量级，两层枚举一亿次在极端数据下会踩到时限边缘，而且题目给的是「值域有限的整数」，这两个信号合起来提示：应该按值直接定位对方需要的那一盒，而不是逐对比较。

边界上要注意两侧数组长度可以完全不同，糖果大小可以重复，也可能出现「换出去的和换回来的大小相同」这种平局情况。

解法：总和差值 + 哈希集合

核心思路

最直接的写法是双重循环：枚举 Alice 换出的每一盒 x，再枚举 Bob 换出的每一盒 y，检查交换后两边是否相等。瓶颈在于内层循环把「验证」和「查找」混在一起，每次都重新扫一遍 Bob 的全部糖果，总代价是 $O(mn)$。

关键观察是：内层循环要找的 y 其实不是「某个满足复杂条件的数」，而是一个唯一确定的数。设 Alice 总量 sumA、Bob 总量 sumB，交换 x 与 y 后两边分别是 sumA - x + y 和 sumB - y + x，令二者相等并整理，得到 2(x - y) = sumA - sumB，即 $y = x - (sumA - sumB) / 2$。

换句话说，一旦固定了 Alice 换出的 x，Bob 必须换出的 y 就被完全锁死了，不存在多个候选。于是问题从「找一对」退化成「对每个 x，判断某个具体数值是否在 Bob 的糖果里」，内层循环被一次查询取代。

由此可以写出算法的不变量：记 diff = (sumA - sumB) / 2，则一组交换 (x, y) 合法当且仅当 y == x - diff 且 y ∈ bobSizes。只要把 Bob 的糖果预先装进一个支持 $O(1)$ 存在性判断的集合，整个扫描就是线性的。

这里还隐含一个前提：sumA - sumB 必须是偶数。题目保证有解，说明这一点自动成立，不需要额外校验。

解题步骤

先求出 Alice 的总量 sumA。它决定了差值 diff，是后续所有推导的输入；单独一次遍历即可，不需要和别的逻辑耦合。

遍历 Bob 的糖果，同时累加 sumB 并把每盒大小放进集合。之所以合并成一趟，是因为这两件事都只依赖 Bob 的数据，没有先后依赖；集合的作用是把后面的「y 是否存在」从线性扫描降到常数判断。

计算 diff = (sumA - sumB) / 2。注意这里用的是有符号整除：当 Alice 比 Bob 多时 diff 为正，说明 Alice 要换出更大的糖果；反之 diff 为负，Alice 要换出更小的。写成减法而不是加法，是为了让后面统一用 target = size - diff 一个式子处理两种方向。

扫描 Alice 的每盒糖果 size，检查 size - diff 是否在集合中。命中就立刻返回 [size, size - diff]。之所以可以立刻返回，是因为题目允许任意一组答案，第一组和最后一组等价，没有必要继续找。

循环结束返回空数组。理论上题目保证有解不会走到这一行，但函数必须有返回值，保留兜底分支比抛异常更省事。

以 aliceSizes = [1, 2, 5], bobSizes = [2, 4] 走一遍：先算 sumA = 1 + 2 + 5 = 8。再遍历 Bob，sumB = 2 + 4 = 6，集合变成 {2, 4}。diff = (8 - 6) / 2 = 1，含义是 Alice 换出的糖果要比换回来的大 1。接着扫 Alice：size = 1 时 target = 1 - 1 = 0，集合里没有 0，跳过；size = 2 时 target = 2 - 1 = 1，集合里没有 1，跳过；size = 5 时 target = 5 - 1 = 4，命中集合，返回 [5, 4]。验算一下：Alice 换出 5 换回 4，总量变成 8 - 5 + 4 = 7；Bob 换出 4 换回 5，总量变成 6 - 4 + 5 = 7，两边相等，答案正确。

代码实现

// 若 Alice 换出 x，Bob 换出 y，需要满足 sumA - x + y = sumB - y + x。
class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int sumA = 0;
        for (int size : aliceSizes) {
            sumA += size;
        }

        int sumB = 0;
        Set<Integer> bobSet = new HashSet<>();
        for (int size : bobSizes) {
            sumB += size;
            bobSet.add(size);
        }

        int diff = (sumA - sumB) / 2;
        for (int size : aliceSizes) {
            int target = size - diff;
            if (bobSet.contains(target)) {
                return new int[] {size, target};
            }
        }

        return new int[0];
    }
}

// 若 Alice 换出 x，Bob 换出 y，需要满足 sumA - x + y = sumB - y + x。
func fairCandySwap(aliceSizes []int, bobSizes []int) []int {
    sumA := 0
    for _, size := range aliceSizes {
        sumA += size
    }

    sumB := 0
    bobSet := make(map[int]bool)
    for _, size := range bobSizes {
        sumB += size
        bobSet[size] = true
    }

    diff := (sumA - sumB) / 2
    for _, size := range aliceSizes {
        target := size - diff
        if bobSet[target] {
            return []int{size, target}
        }
    }

    return []int{}
}

复杂度分析

时间复杂度：$O(m + n)$。求 sumA 扫一遍 Alice 是 $O(m)$，建集合并求 sumB 扫一遍 Bob 是 $O(n)$，最后再扫一遍 Alice 每次做一次常数期望的存在性判断，仍是 $O(m)$，三段相加即为 $O(m + n)$。

空间复杂度：$O(n)$。额外开销只有装 Bob 全部糖果的集合，最坏情况下 n 个元素互不相同全部保留；返回的结果数组固定长度 2，不计入增长量。

关键点总结

把「找一对」化成「找一个」：只要两个未知量之间存在线性约束，固定其中一个就能解出另一个，双重循环立刻塌缩成单层循环加查表。这是所有「两数之和」型题目的公共骨架，遇到「交换/配对使某个统计量相等」先往这个方向推。

先列方程再写代码：sumA - x + y = sumB - y + x 这一步是本题唯一的思维成本，推错方向（比如漏掉系数 2）会让整份代码都是错的。面试时把这个等式写在白板上再动手，既降低出错概率，也直接展示了推导过程。

利用题目保证的性质换取代码简洁：题目承诺有解，于是「差为偶数」「一定能命中」都不必校验。面试中主动说出「因为题目保证有解，所以这里不做整除性检查」，比默默省略更能体现严谨。

值域有限是使用哈希/计数结构的信号：糖果大小上限固定，说明可以用值本身当键。若面试官追问优化，可以把哈希集合换成布尔数组，常数更小且没有哈希冲突风险。

允许返回任意解时立即短路：不要为了「找最优」而扫完全程，明确题目是否需要全部解，直接影响能不能提前 return。

面试视角：这题真正的考点不是数据结构，而是能否把业务描述翻译成代数式。给出 $O(m + n)$ 解法后，主动补一句「两个数组若都已排序，还能用双指针做到 $O(1)$ 额外空间」，会显著加分。

易错点总结

错误写法：把 diff 算成 sumA - sumB 忘记除以 2。用例 aliceSizes = [1, 2, 5], bobSizes = [2, 4] → diff 变成 2，扫描时 target 依次为 -1、0、3，全部落空，函数返回空数组，判题直接判错。

错误写法：把 target 写成 size + diff。同样用例下 target 依次为 2、3、6，第一个 size = 1 就命中 2，返回 [1, 2]。验算：Alice 变成 8 - 1 + 2 = 9，Bob 变成 6 - 2 + 1 = 5，两边根本不等，返回了一个非法解。

错误写法：用 Bob 的元素去减 diff、在 Alice 集合里查。用例同上会得到 [4, 5]，顺序颠倒。题目要求返回数组第一位是 Alice 换出的糖果，位置反了会被判错，而不是「答案等价」。

错误写法：累加总和时用 int 但先做乘法或没意识到规模。若数组长度 10^4、单个糖果 10^5，总和上限约 10^9，仍在 int 范围内，但如果照搬到加强版（长度 10^5）就会溢出成负数，diff 随之变号，返回错误配对。稳妥做法是 Java 用 long 累加、Go 的 int 本身是 64 位无需担心。

错误写法：认为两边总和相等时可以直接返回空或不交换。用例 aliceSizes = [1, 1], bobSizes = [1, 1] → diff = 0，正确答案是 [1, 1]（换一盒同样大小的）。如果加了「diff == 0 就 return new int[0]」的短路，会漏掉这组合法答案。

错误写法：把 Bob 的糖果装进 List 后用 contains 查找。用例是两边各 10^4 个元素，List.contains 是线性扫描，总复杂度退回 $O(mn)$ 约一亿次比较，在极端数据下超时；必须用 HashSet 或数组下标标记。

错误写法：Go 里用 map[int]bool 但查存在性时写成 _, ok := bobSet[target] 之后误判。若集合中存过 bobSet[x] = false（例如复制粘贴时写反了赋值），ok 为真但语义为假，用例 bobSizes = [2, 4] 会让所有 target 都「命中」，返回第一个 size 组成的非法解。要么统一存 true，要么改用 map[int]struct{}。

错误写法：找到答案后继续循环，用后面的结果覆盖前面的。虽然本题任意解都算对，但多余的遍历在「返回字典序最小」的变体里会直接出错，且白白浪费一次全扫描；养成命中即 return 的习惯。

相似题目

题目	难度	考察点
1. 两数之和	简单	同样是「固定一个数解出另一个」，但目标值直接给出，无需先由总和差推导
454. 四数相加 II	中等	把四个数组折半配对，用计数而非存在性，考察分组哈希的取舍
170. 两数之和 III - 数据结构设计	简单	数据动态插入，重点在 add 与 find 的复杂度如何分摊
560. 和为 K 的子数组	中等	键从元素值换成前缀和，且需要统计出现次数而不是判断是否存在