888. Fair Candy Swap

class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int aliceSum = 0;
        for (int size : aliceSizes) {
            aliceSum += size;
        }
        int bobSum = 0;
        for (int size : bobSizes) {
            bobSum += size;
        }

        int targetSum = (aliceSum + bobSum) / 2;
        int targetDiff = targetSum - aliceSum;
        Arrays.sort(aliceSizes);
        Arrays.sort(bobSizes);

        for (int i = 0; i < aliceSizes.length; i++) {
            if (i > 0 && aliceSizes[i] == aliceSizes[i - 1]) {
                continue;
            }
            int targetIndex = Arrays.binarySearch(bobSizes, aliceSizes[i] + targetDiff);
            if (targetIndex >= 0) { // 注意找不到元素时，返回的不一定是 -1
                return new int[]{aliceSizes[i], bobSizes[targetIndex]};
            }
        }

        return new int[0];
    }
}

二分查找的前提是有序，所以我们进行了排序操作再使用二分查找。

Hash

class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        int aliceSum = 0;
        for (int size : aliceSizes) {
            aliceSum += size;
        }

        int bobSum = 0;
        Set<Integer> set = new HashSet<>();
        for (int size : bobSizes) {
            bobSum += size;
            set.add(size);
        }

        int targetSum = (aliceSum + bobSum) / 2;
        int targetDiff = targetSum - aliceSum;
    
        for (int i = 0; i < aliceSizes.length; i++) {
            int exceptedBobSize = aliceSizes[i] + targetDiff;
            if (set.contains(exceptedBobSize)) {
                return new int[]{aliceSizes[i], exceptedBobSize};
            }
        }

        return new int[0];
    }
}

另一种更高效的实现方式是采用哈希表。

References

888. Fair Candy Swap