leet code 888.公平的糖果交换

888.公平糖果交换

题目解析

• 题目中给定了两个数组，而并没有明确给定数组是否已经排序，所以需要先对目标数组进行排序
• 然后需要计算两个数组的差值，从而确定哪一方交换出更多的糖果，即 爱丽丝 或 鲍勃 那一方 付出更多的糖果
• 假设其中一方需要付出较多的糖果数量记为
• 另一方需要付出较少的糖果数量记为
• 那么有

• 为什么是
• 假设 爱丽丝 一共有 10 个糖果，鲍勃有 8 个糖果，他们相差了 两个糖果。
• 10 - 爱丽丝付出的糖果 + 鲍勃付出的糖果 = 9
• 即，爱丽丝付出的糖果数 - 鲍勃付出的糖果数 = （爱丽丝的糖果数 - 鲍勃的糖果数）/ 2

• 因此需要从付出较多糖果的一方寻找 大于 的元素 ，判断其是否可以找到匹配的

• 从而满足

• 运用二分查找，轻松解决问题！

show code

public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        Arrays.sort(aliceSizes);
        Arrays.sort(bobSizes);

        int sum_alice = Arrays.stream(aliceSizes).sum();
        int sum_bob = Arrays.stream(bobSizes).sum();

        if(sum_alice > sum_bob) {
            int diff = sum_alice - sum_bob;
            // 爱丽丝 需要交换出更多的糖果--去交换鲍勃较少的糖果.

            for (int aliceSize : aliceSizes) {
                // 需要减少的糖果数量是 diff / 2
                if(aliceSize < diff / 2) {
                    continue;
                }
                // 从 bobSizes 数组中寻找元素  aliceSize - diff / 2
                int i = binarySearch(bobSizes, aliceSize - diff / 2);
                if(i != -1) {
                    return new int[]{aliceSize, i};
                }
            }
        } else {
            int diff = sum_bob - sum_alice;
            // 鲍勃 付出更多的糖果 -- 去交换 爱丽丝较少的糖果.
            for (int bobSize : bobSizes) {
                if(bobSize < diff / 2) {
                    continue;
                }
                // 从 aliceSizes 数组中寻找元素  bobSize - diff / 2
                int i = binarySearch(aliceSizes, bobSize - diff / 2);
                if(i != -1) {
                    return new int[]{i, bobSize};
                }
            }
        }

        return null;
    }

    private int binarySearch(int[] sizes, int target) {
        int n = sizes.length;
        int left = 0,right = n -1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(sizes[mid] == target) {
                return target;
            } else if(sizes[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }