目标
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回能够实现数组相等的 最小 整数 x 。
示例 1:
输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]
输出：-2
解释：移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。示例 2:
输入：nums1 = [3,5,5,3], nums2 = [7,7]
输出：2
解释： 移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。说明：
- 3 <= nums1.length <= 200
- nums2.length == nums1.length - 2
0 <= nums1[i], nums2[i] <= 1000- 测试用例以这样的方式生成：存在一个整数 x，nums1 中的每个元素都与 x 相加后，再移除两个元素，nums1 可以与 nums2 相等。
思路
这与找出与数组相加的整数 I类似，只不过需要删除nums1中的两个元素，这样x就可能存在多个值，取其中最小的。
最简单的想法是将这两个数组排序，枚举 nums1 长度为 2 的子序列组合，将其从数组中删去，判断对应位置上的 nums2[i] - nums1[i] 的值是否都等于 x。如果相等则保存，枚举完所有子序列组合后取保存的最小值即可。排序的时间复杂度为 O(nlogn) 代入 n = 200 大约 460.2，子序列可能的组合有 C(200, 2) = 19900，针对每种组合都要遍历数组，循环 200 次，大概需要执行 200 * 19900 ≈ 4 * 10^6 次，应该不会超时。
可以将 nums2 与 nums1 中的元素两两相减然后统计差值的出现次数，如果出现次数小于 nums2.length 那么该差值一定不是 x。因为 nums1.length - 2 == nums2.length，如果 x 存在，那么其出现次数最少为nums2.length。例如，[1,2,3,4] 与 [3,4] 的差值 2 1 0 -1 3 2 1 0 2出现了2次，1出现了2次，0出现了2次，取最小的0。
得到了可能的 x 之后，我们需要判断是否合法，例如 [9,9,1,1,1] 与 [5,5,5], 差值 -4 出现了 6 次，4 出现了 9 次。但是 -4 是不合法的，因为使用 nums2 - (-4) 还原回去的个数对不上。
看官网题解 // todo
代码
/**
* @date 2024-08-09 0:30
*/
public class MinimumAddedInteger3132 {
public int minimumAddedInteger(int[] nums1, int[] nums2) {
int n = nums2.length;
Map<Integer, Integer> map = new TreeMap<>();
Map<Integer, Integer> set = new HashMap<>(nums1.length);
for (int i : nums1) {
set.merge(i, 1, Integer::sum);
}
for (int v2 : nums2) {
for (int v1 : nums1) {
map.merge(v2 - v1, 1, Integer::sum);
}
}
int res = Integer.MAX_VALUE;
here:
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Map<Integer, Integer> tmp = new HashMap<>(set);
if (entry.getValue() >= n) {
for (int i : nums2) {
if (tmp.get(i - entry.getKey()) == null || tmp.get(i - entry.getKey()) <= 0) {
continue here;
}
tmp.merge(i - entry.getKey(), -1, Integer::sum);
}
res = Math.min(res, entry.getKey());
}
}
return res;
}
}