LeetCode 888 - Fair Candy Swap

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

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]

Approach 1: Solve the Equation

Intuition

If Alice swaps candy x, she expects some specific quantity of candy y back.

Algorithm

Say Alice and Bob have total candy $S_A, S_B$ respectively.

If Alice gives candy $x$, and receives candy $y$, then Bob receives candy $x$ and gives candy $y$. Then, we must have

$S_A - x + y = S_B - y + x$

for a fair candy swap. This implies

$y = x + \frac{S_B - S_A}{2}$

Our strategy is simple. For every candy $x$ that Alice has, if Bob has candy $y = x + \frac{S_B - S_A}{2}$, we return $[x, y]$. We use a Set structure to check whether Bob has the desired candy $y$ in constant time.

• Time Complexity: $O(A\text{.length} + B\text{.length})$.
• Space Complexity: $O(B\text{.length})$, the space used by setB. (We can improve this to $\min(A\text{.length}, B\text{.length})$ by using an if statement.) 

    public int[] fairCandySwap(int[] A, int[] B) {

        int sa = 0, sb = 0;  // sum of A, B respectively

        for (int x: A) sa += x;

        for (int x: B) sb += x;

        int delta = (sb - sa) / 2;

        // If Alice gives x, she expects to receive x + delta

        Set<Integer> setB = new HashSet();

        for (int x: B) setB.add(x);

        for (int x: A)

            if (setB.contains(x + delta))

                return new int[]{x, x + delta};

        throw null;

    }

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

Calculate dif = (sum(A) - sum(B)) / 2
We want find a pair (a, b) with a = b + dif

    public int[] fairCandySwap(int[] A, int[] B) {
        int dif = (IntStream.of(A).sum() - IntStream.of(B).sum()) / 2;
        HashSet<Integer> S = new HashSet<>();
        for (int a : A) S.add(a);
        for (int b : B) if (S.contains(b + dif)) return new int[] {b + dif, b};
        return new int[0];
    }

https://leetcode.com/problems/fair-candy-swap/discuss/161316/Java-2-solutions-clear-explanation-with-illustration

Therefore, our target is to find a candy pair whose difference is exactly x/2
if B > A, logic is exactly the same

Sol1 Brute Force

time complexity:O(A + B + A * B)
space complexity:O(1)

    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = 0, sumB = 0;
        for (int i = 0; i < A.length; i++)
            sumA += A[i];
        for (int i = 0; i < B.length; i++)
            sumB += B[i];
        int dif = (sumA - sumB) / 2;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (A[i] - B[j] == dif)
                    return new int[]{A[i], B[j]};
            }
        }
        return null;
    }

https://blog.csdn.net/XX_123_1_RJ/article/details/81913029

题目说的很明白了，一定有答案。我们设：Alice和Bob 分别拿出的是x、y，所以有：

sum(A) - x + y = sum(B) - y + x
y = (sum(B) - sum(A))/2 + x

https://blog.csdn.net/fuxuemingzhu/article/details/82013077
看了一眼A,B数组的范围就知道，时间复杂度一定不能太高。我们分析一下可以看出，交换之后A,B数组的和都应该是相同的，也就是两个数组和的平均数。

所以对数组A进行遍历，那么对于每个数字，得到除去该数值以外其他数字的和；使用平均数减去这个和，看这个结果是否在数组B中，如果在返回即可。

也就是说，通过上面的方法，我们使得数组A的和等于平均数，这种情况下，数组B的和也为平均数。