This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 888 on LeetCode. Fair candy bar exchange.

Tag: Hash table

Alice and Bob have different sizes of candy bars: A[I] is the size of Alice’s i-th candy bar, and B[j] is the size of Bob’s J-th candy bar.

Because they are friends, they want to exchange a candy bar so that after the exchange, they both have the same amount of candy. (The total amount of candy a person owns is the total number of candy bars they own.)

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

If there are more than one answer, you can return any one of them.

Make sure the answer exists.

Example 1:

Input: A = [1,1], B = [2,2]Copy the code

Example 2:

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

Example 3:

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

Example 4:

Input: A = [1,2,5], B = [2,4] output: [5,4]Copy the code

Tip:

  • 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.
  • There must be an answer.

Simple solution

The ultimate goal is to make the sum of the two arrays equal.

So we can get the sum of the two arrays as aSumaSumaSum and bSumbSumbSum.

Total =aSum+bSumtotal =aSum+bSumtotal =aSum+bSumtotal =aSum+bSum

Target =total/2target =total/2target =total/2.

The difference between the two arrays and the target sum is target− ASumtarget-asumtarget −aSum and target− bsumtarget-bsumtarget −bSum.

Diff =target−aSumdiff =target – aSumdiff=target−aSum.

For a a [I] a [I] a [I], if a [I] a [I] a [I] can constitute the answer, then b in the array size is there must be a [I] + diffa diffa [I] + [I] + diff values, make both exchange, The array summation is targettargettarget.

Therefore, we just need to traverse the array A and find which a[I]a[I]a[I]a[I]a[I] makes a[I]+ Diffa [I]+diff exist in array B.

Code:

class Solution {
    public int[] fairCandySwap(int[] a, int[] b) {
        int aSum = 0, bSum = 0;
        for (int i : a) aSum += i;  
        for (int i : b) bSum += i;  
        int total = aSum + bSum, target = total / 2;
        int diff = target - aSum;
        int[] ans = new int[2];
        for (int i : a) {
            if (find(b, i + diff)) {
                ans[0] = i;
                ans[1] = i + diff; }}return ans;
    }
    boolean find(int[] nums, int target) {
        for (int i : nums) {
            if (i == target) return true;
        }
        return false; }}Copy the code
  • Time complexity: Calculate the total complexity O(n)O(n)O(n) O(n), find the final complexity O(n2)O(n^2)O(n2). Overall complexity O(n2)O(n^2)O(n2)
  • Space complexity: O(1)O(1)O(1)

To find the optimal

The above solution cannot be linear because each time we scan array B to determine whether a[I]+ Diffa [I]+ Diffa [I]+diff exists.

We know that map/set/ array can do O(1)O(1)O(1) lookups. Since we specify the range of numbers in both arrays, we can count using arrays.

At the same time, you can optimize the use of variables, using a variable called Diffdiffdiff to calculate the final difference value.

This kind of optimization is a typical space for time.

Code:

class Solution {
    public int[] fairCandySwap(int[] a, int[] b) {
        // Find the sum of a
        int diff = 0;
        for (int i : a) diff += i;  

        // Use CNT to count the number of occurrences in b, and calculate the difference between the sum of A and b
        int[] cnt = new int[100009];
        for (int i : b) {
            diff -= i;
            cnt[i]++;
        }

        // Calculate the exact substitution difference in a
        diff /= -2;
        int[] ans = new int[2];
        for (int i : a) {
            int target = i + diff;
            // If the target substitution is in the legal range and exists in the B array. That means we have a solution
            if (target >= 1 && target <= 100000 && cnt[target] > 0) {
                ans[0] = i;
                ans[1] = target;
                break; }}returnans; }}Copy the code
  • Time complexity: Calculate the total complexity of O(n)O(n)O(n) O(n), find the final complexity of O(n)O(n)O(n) O(n). The overall complexity is O(n)O(n)O(n)
  • Space complexity: UsecntArray counts. Complexity of
    O ( n ) O(n)

The last

This is the 888th article in our “Brush through LeetCode” series. The series started on 2021/01/01. By the start date, there are 1916 topics in LeetCode, some of which have locks, so we will finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.