Look at the problem and prepare

Today’s introduction to LeetCode algorithm is Easy level 208 (sequence number is 888). Alice and Bob have different sizes of candy bars: A[I] is the size of the ith candy bar that Alice owns, and B[j] is the size of the jith candy bar that Bob owns.

Since they are friends, they want to exchange a candy so that after the exchange, they both have the same total amount of candy. (The total amount of candy a person owns is the sum of the size of the candy they own.)

Returns an array of integers ans, where ANS [0] is the size of the candy that Alice must exchange and ans[1] is the size of the candy that Bob must exchange.

If there are more than one answer, you can return any one of them. The answer is guaranteed to exist. Such as:

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

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

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

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

Make sure Alice and Bob have different amounts of candy.

The answer is guaranteed.

The first solution

If Alice and Bob have different amounts of candy, the answer must exist. The difference between their total amount of candy must be an even number. Only if the difference is even, the difference is divided to get an average value.

Therefore, we only need to find the average value of the difference between the total amount of candy between the Two people, and then take the average value plus the size of any candy in one party to match the size of the candy in the other party. If they can match, it means that the Two candies need to be exchanged. In this situation, the problem is somewhat similar to Two sums.

    public int[] fairCandySwap(int[] A, int[] B) {
        // Store the elements of A (or B)
        Set<Integer> set = new HashSet<>();
        int[] result = new int[2];
        int sumA = 0;
        for (int a : A) {
            sumA += a;
            set.add(a);
        }
        int sumB = 0;
        for (int b : B) {
            sumB += b;
        }
        // The average difference between the total amount of candy between two people
        int num = (sumA - sumB) / 2;
        // Iterate over the elements in B, add the average of the differences to the other array,
        // If a match is found, the element that needs to be swapped is encountered.
        for (int b : B) {
            if (set.contains(b + num)) {
                return new int[]{b + num, b}; }}return result;
    }
Copy the code

Second solution

Instead of using the HashSet in the first solution, we can use A different data structure, using A Boolean array to store the values in A. The wrapper class Boolean is set to null by default, while the underlying type Boolean is set to false by default

public int[] fairCandySwap(int[] A, int[] B) {
        int[] result = new int[2];
        boolean[] set = new boolean[100001];
        int sumA = 0;
        for (int a : A) {
            sumA += a;
            set[a] = true;
        }
        int sumB = 0;
        for (int b : B) {
            sumB += b;
        }
        int num = (sumA - sumB) / 2;
        for (int b : B) {
            if (b + num > 0 && b + num < 100001 && set[b + num]) {
                return new int[]{b + num, b}; }}return result;
    }
Copy the code