leetcode
leetcode 2851 ~ 2900
交换和

交换和

难度:

标签:

题目描述

Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.

Return an array, where the first element is the element in the first array that will be swapped, and the second element is another one in the second array. If there are more than one answers, return any one of them. If there is no answer, return an empty array.

Example:

Input: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
Output: [1, 3]

Example:

Input: array1 = [1, 2, 3], array2 = [4, 5, 6]
Output: []

Note:

  • 1 <= array1.length, array2.length <= 100000

代码结果

运行时间: 33 ms, 内存: 19.9 MB


/*
 * 思路:
 * 1. 计算两个数组的总和。
 * 2. 如果两个数组的总和之差不是偶数,则不可能通过交换使它们相等,直接返回空数组。
 * 3. 使用一个哈希集合来存储较小数组的元素。
 * 4. 使用Java Stream API遍历较大数组的每个元素,检查是否存在一个对应的元素在较小数组中,使得交换后两个数组的和相等。
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        int sum1 = Arrays.stream(array1).sum();
        int sum2 = Arrays.stream(array2).sum();

        if ((sum1 - sum2) % 2 != 0) return new int[0];

        int target = (sum1 - sum2) / 2;
        Set<Integer> set = new HashSet<>();
        Arrays.stream(array1).forEach(set::add);

        return Arrays.stream(array2)
                .filter(num -> set.contains(num + target))
                .mapToObj(num -> new int[]{num + target, num})
                .findFirst()
                .orElse(new int[0]);
    }
}

解释

方法:

此题目要求从两个数组中各选一个数进行交换,使得交换后两数组的总和相等。首先,我们计算两数组之和的差值 diff = sum(array1) - sum(array2)。如果我们从 array1 中选一个值 a 从 array2 中选一个值 b 进行交换,使得 sum(array1) - a + b = sum(array2) - b + a,这意味着 2a - 2b = diff,即 a - b = diff / 2。因此,对于 array1 中的每个元素 a,我们计算 b = a - diff / 2,然后检查 b 是否存在于 array2 中。为了快速查找,我们可以将 array2 的元素存储在一个集合中。如果找到符合条件的 a 和 b,返回 [a, b];否则返回一个空数组。

时间复杂度:

O(n)

空间复杂度:

O(n + m)

代码细节讲解

🦆
在计算变量`b`时,为什么选择使用`b = (2 * a - diff) / 2`这种形式,它与直接求解`a - b = diff / 2`相比有什么优势吗?
选择使用`b = (2 * a - diff) / 2`这种形式是为了避免出现浮点数运算。在编程语言中,如果`diff`是奇数,除以2会产生小数,这可能导致查找不准确或类型不匹配的错误。通过首先计算`2 * a - diff`,然后除以2,确保了所有的运算都在整数域内进行,从而避免了这种问题。这种方法同时也确保了只在整数解是有效的时候才进行查找,避免了无效的计算和查找。
🦆
代码中如何处理`diff`为奇数的情况,因为这种情况下`(diff / 2)`不再是整数,这对计算`b`的值有何影响?
代码中通过计算`2 * a - diff`并检查结果是否可以被2整除来处理`diff`为奇数的情况。如果`2 * a - diff`是偶数,这意味着`diff`将不会影响`b`的整数性。这种方法确保了即使`diff`为奇数,计算出的`b`也总是整数。这样的处理避免了因`diff`为奇数而导致的非整数`b`值的问题,从而确保`b`总是有效的且可以在数组中查找到。
🦆
题解提供的算法在遍历`set1`时,是否考虑了所有可能的`a`值,即直接从`array1`遍历与从`set1`遍历有何不同?
遍历`set1`与直接遍历`array1`的主要区别在于`set1`是`array1`的去重版本。使用集合来遍历的优点是避免了重复元素的多次检查,提高了算法的效率。然而,这种方法假设每个元素至多只需要交换一次即可达到题目要求。如果`array1`中有重复元素可能多次参与到解中,这种情况下直接遍历`array1`可能会有不同的结果。但对于本题的需求,考虑每个元素一次就足够了,因此使用`set1`可以减少不必要的计算和查找,加快解题速度。

相关问题