[LeetCode] 888. Fair Candy Swap 公平糖果交换

时间：2021-01-22 19:36:53

Alice and Bob have candy bars of different sizes: `A[i]` is the size of the `i`-th bar of candy that Alice has, and `B[j]` is the size of the `j`-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar each so that after the exchange, they both have the same total amount of candy.  (The total amount of candy a person has is the sum of the sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them.  It is guaranteed an answer exists.

Example 1:

Input: A = [1,1], B = [2,2]

Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]

Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]

Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]

Output: [5,4]

Note:

  • 1 <= A.length <= 10000
  • 1 <= B.length <= 10000
  • 1 <= A[i] <= 100000
  • 1 <= B[i] <= 100000
  • It is guaranteed that Alice and Bob have different total amounts of candy.
  • It is guaranteed there exists an answer.

这道题说爱丽丝和鲍勃两人有不同大小的糖果，现在要让两人交换一个糖果，使得交换后两人的糖果总重量相同，而且限定了两人初始时的糖果总量不相同，并且一定会有解。若我们仔细观察题目中给的例子，可以发现所有例子中起始时 Alice 和 Bob 两人的糖果总重量的差值一定时偶数，这是 make sense 的，因为最终两人的糖果总量时要相同的，那么起始时的重量差就应该能平均分为两部分，一部分来弥补轻的一方，一部分来抵消重的一方。那么有了这个 diff，我们只需要在两个数组中查找差值为 diff 的两个数字了，其实就是 [Two Sum](http://www.cnblogs.com/grandyang/p/4130379.html) 的变种，使用一个 HashSet 先来保存数组 A 中所有的数字，然后遍历数组B中的每个数字 num，查找 HashSet 中否存在 num+diff 即可，参见代码如下：

class Solution {

public:

    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {

		int diff = (accumulate(A.begin(), A.end(), 0) - accumulate(B.begin(), B.end(), 0)) / 2;

		unordered_set<int> st(A.begin(), A.end());

		for (int num : B) {

			if (st.count(num + diff)) return {num + diff, num};

		}

		return {};

    }

};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/888

类似题目：

Two Sum

参考资料：

https://leetcode.com/problems/fair-candy-swap/

https://leetcode.com/problems/fair-candy-swap/discuss/161269/C%2B%2BJavaPython-Straight-Forward

[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)

相关文章