交换和
难度:
标签:
题目描述
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`相比有什么优势吗?
▷🦆
代码中如何处理`diff`为奇数的情况,因为这种情况下`(diff / 2)`不再是整数,这对计算`b`的值有何影响?
▷🦆
题解提供的算法在遍历`set1`时,是否考虑了所有可能的`a`值,即直接从`array1`遍历与从`set1`遍历有何不同?
▷