LeetCode 888. 公平的糖果交换

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 华为
标签
数组 哈希表 排序 二分查找

题目描述

✅ 888. 公平的糖果交换

image-20260928225306324

image-20260928225306325

题意分析

Alice 和 Bob 各拿出一盒糖果交换，使交换后的糖果总量相等。返回两个盒子的糖果数量，顺序为 Alice、Bob，不是返回盒子的下标。题目保证至少存在一组答案，找到任意一组即可。

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

核心思路

[!blue]

设双方原总量为 sumA、sumB，Alice 换出 x，Bob 换出 y。交换后的总量分别为 sumA - x + y 和 sumB - y + x，要求两者相等，整理得到 2 * (x - y) = sumA - sumB。

令 diff = (sumA - sumB) / 2，那么选定 Alice 的盒子 x 后，Bob 必须提供的数量唯一确定为 y = x - diff。题目保证有整数答案，所以总量差一定是偶数，这里的整除不会丢失信息。

将 Bob 所有盒子的数量存入哈希集合，再枚举 Alice 的每个盒子，查询对应的 y 是否存在。命中时等式成立，交换一定可行；所有 Alice 盒子都被枚举，因此也不会漏掉题目保证存在的答案。每人只选择一盒，集合只需保存存在性，无需统计相同数量有几盒。

解题步骤

  • 计算 sumA、sumB，同时把 Bob 的盒子数量加入集合。
  • 计算有正负号的半差 diff，不能取绝对值。
  • 依次取 Alice 的盒子数量 x，计算 y = x - diff。
  • 若集合中存在 y，返回 [x, y]。题目保证有解，合法输入一定会在枚举过程中返回。

代码实现

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) {
            // 当前 Alice 盒子唯一对应的 Bob 盒子大小。
            int target = size - diff;

            if (bobSet.contains(target)) {
                return new int[] {
                    size,
                    target
                };
            }
        }

        return new int[0];
    }
}

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 {
        // 当前 Alice 盒子唯一对应的 Bob 盒子大小。
        target := size - diff
        if bobSet[target] {
            return []int{
                size,
                target,
            }
        }
    }

    return []int{
    }
}

复杂度分析

设 Alice、Bob 分别有 m、n 盒糖果。

  • 时间复杂度：期望 $O(m+n)$。求和、建集合和枚举各扫描一次数组，集合查询期望为 $O(1)$。
  • 空间复杂度：$O(u_B)$，u_B 为 Bob 的不同盒子数量值的个数，最多为 n。

关键点总结

[!green]

  • 一次交换同时改变双方总量，总量差因此变化两倍，必须先除以 2。
  • 平衡等式把两两枚举变成“固定一方，查询另一方唯一候选”。
  • 相同大小的盒子只需在集合中出现一次，仍然足以提供一盒用于交换。

易错点总结

[!yellow]

  • diff 定义为 Alice 总量减 Bob 总量的一半，对应候选必须是 x - diff，不能反向相加。
  • 不能对总量差取绝对值，否则会丢失哪一方需要换出更多糖果的信息。
  • 返回的是 [Alice 的数量, Bob 的数量]，交换顺序或返回下标都不符合要求。

相似题目

题目 难度 关联与区别
面试题 16.21. 交换和 中等 等式化简相同，原题支持一般整数数组，本题元素是正糖果数量。
1. 两数之和 简单 固定一边数值后，交换平衡等式给出另一边唯一候选，可用哈希集合查询。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/76319998
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！