公平的糖果棒交换

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，888. Fair Candy Swap

先看题目描述

yZPOw8.png

大意就是给定两个数组 A 和 B 代表两个人所拥有的糖果的大小，一个人所拥有的糖果总量是这个人所拥有的糖果大小之和，让我们交换这两个人所拥有的一个糖果，使得两人拥有的糖果总量相等，并返回交换的糖果的大小

算法和思路

设 A 的元素之和为 sumA，B 的元素之和为 sumB，交换的糖果为 {x，y}，那么就会满足该等式：sumA - x + y = sumB - y + x，转化得到 (sumA - sumB) / 2 = x - y，令 target = (sumA - sumB) / 2，那么就是要找到 x 和 y 满足 x - y = target

排序和双指针

这是第一反应想到的方法

先将数组 A 和 B 升序排列，再初始化两个指针 i 和 j 分别指向数组 A 和 B 的第一个元素，然后进行判断：

  • 若 A[i] - B[j] 等于 target，那么就找到了答案
  • 若 A[i] - B[j] 大于 target，则将指针 j 右移
  • 若 A[i] - B[j] 小于 target，则将指针 i 右移

哈希表

先将 A 中的元素都存入一个哈希表中，然后遍历 B 中的元素，当遍历到元素 y 时，进行判断，若哈希表中存在 y + target，那么就找到了答案，直接返回 {y + target，y}

算法源码

排序和双指针

Arrays.stream(A).sum() 是对数组求和的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int m = A.length;
        Arrays.sort(A);
        Arrays.sort(B);
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        int target = (sumA - sumB) / 2;
        int j = 0;
        for (int i = 0; i < m; i++) {
            while ((A[i] - B[j]) > target) {
                j++;
            }
            if ((A[i] - B[j]) == target) {
                return new int[]{A[i], B[j]};
            }
        }
        return new int[]{0, 0};
    }
}

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = Arrays.stream(A).sum();
        int sumB = Arrays.stream(B).sum();
        int target = (sumA - sumB) / 2;
        Set<Integer> set = new HashSet<>();
        for (int x : A) {
            set.add(x);
        }
        for (int y : B) {
            int tar = y + target;
            if (set.contains(tar)) {
                return new int[]{tar, y};
            }
        }
        return new int[]{0, 0};
    }
}