Leetcode 第 395 场周赛 3132. 找出与数组相加的整数 II_给你两个整数数组 nums1 和 nums2。 从 nums1 中移除两个元素,并且所有其他元素都

给你两个整数数组 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 相等。

思路：分析题意，枚举两个删除的数，然后判断剩下的加上某个数是不是和数组2相等。
缺点：代码时间复杂度高，如果数据范围大的话会超时。

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int res = 0;
        for(int i = 0; i < nums1.size(); i ++ ) {
            for(int j = i + 1; j < nums1.size(); j ++ ) {
                auto t = nums1;
                t.erase(t.begin() + i);
                t.erase(t.begin() + j - 1);
                bool f = true;
                int x = nums2[0] - t[0];
                for(int k = 0; k < nums2.size(); k ++ ) {
                    if(nums2[k] - t[k] != x) {
                        f = false;
                        break;
                    }
                }
                if(f) return x;
            }
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

思路2：分析得答案是删除2个数后的2个数组的最小值相减，也就是答案在0 1 2 下标中（再不济删除的也就是最小的两个）。因此遍历后面是否存在子数组即可。

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        for(int i = 2; i > 0; i -- ) {
            int diff = nums2[0] - nums1[i];
            int j = 0;
            for(int k = i; k < nums1.size(); k ++ ) {
                if(nums2[j] == nums1[k] + diff && ++j == nums2.size()) {
                    return diff;
                }
            }
        }

        return nums2[0] - nums1[1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19