题目：
给你两个整数数组 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 <= 200nums2.length == nums1.length - 20 <= nums1[i], nums2[i] <= 1000- 测试用例以这样的方式生成：存在一个整数
x，nums1中的每个元素都与x相加后，再移除两个元素，nums1可以与nums2相等。
暴力回溯
思路：
由于这道题属于 nums1 删除两个元素，然后加上 x 与 nums2 相等。
所以我们枚举删除的两个元素，然后判断剩下的 nums1 中的元素是否和 nums2 中的元素差值相同
枚举的方式我们采用回溯
代码：
class Solution {
public:
vector<int> path;
int size; // nums2的大小
int ans = 2000;
int minEleNums2; // nums2的最小元素
void backTrack(vector<int>& nums1, int start, vector<int>& nums2) {
if (path.size() == size) { // 选出了 size 个元素
int x = minEleNums2 - *min_element(path.begin(), path.end());
vector<int> temp = path;
sort(temp.begin(), temp.end());
for (int i = 0; i < size; i++) { // 比对 每个元素差值是否相同
if (temp[i] + x != nums2[i]) {
return;
}
}
ans = min(ans, x); // 更新答案
return;
}
for (int i = start; i < nums1.size(); i++) {
path.push_back(nums1[i]);
backTrack(nums1, i + 1, nums2);
path.pop_back();
}
}
int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
sort(nums2.begin(), nums2.end());
minEleNums2 = nums2[0];
size = nums2.size();
backTrack(nums1, 0, nums2);
return ans;
}
};
排序双指针
思路：
暴力回溯的时间复杂度至少是 O(n^3 * logn)
没有利用到排序这个特性，所以我们先对 nums1 和 nums2 进行排序，由于只能删除两个元素，那么 nums1 中 {0, 1, 2} 三个索引元素中必须选一个，这样就降维了。
通过双指针选取 nums1 和 nums2 中的剩余元素，只要能在 nums1 中找到 nums2 的剩余元素，那么就是答案， x = nums2[0] - nums[idx]
由于要返回最小的 x 那么 idx 应该从 2 向 0 遍历。
代码：
class Solution {
public:
int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int m = nums1.size(), n = nums2.size();
for (int i = 2; i >= 0; i--) {
int left = i + 1, right = 1;
while (left < m && right < n) {
if (nums1[left] - nums2[right] == nums1[i] - nums2[0]) {
right++;
}
left++;
}
if (right == n) { // 全都能找到对应的
return nums2[0] - nums1[i];
}
}
return 2000;
}
};