【面试高频系列】一道简单 & 可优化的开场面试题

输入：A = [1,1], B = [2,2]

输出：[1,2]

输入：A = [1,2], B = [2,3]

输出：[1,2]

输入：A = [2], B = [1,3]

输出：[2,3]

输入：A = [1,2,5], B = [2,4]

输出：[5,4]

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;
    }
}

class Solution {
    public int[] fairCandySwap(int[] a, int[] b) {
        // 先求得 a 的总和
        int diff = 0;
        for (int i : a) diff += i;  

        // 使用 cnt 统计 b 中的数的出现次数，同时计算 a 总和与 b 总和的差值
        int[] cnt = new int[100009];
        for (int i : b) {
            diff -= i;
            cnt[i]++;
        }

        // 计算出 a 中具体的替换差值是多少
        diff /= -2;
        int[] ans = new int[2];
        for (int i : a) {
            int target = i + diff;
            // 如果目标替换量在合法范围，并且存在于 b 数组中。说明找到解了
            if (target >= 1 && target <= 100000 && cnt[target] > 0) {
                ans[0] = i;
                ans[1] = target;
                break;
            }
        }
        return ans;
    }
}