LeetCode 3132.找出与数组相加的整数 II：排序+3次尝试(nlog n)

【LetMeFly】3132.找出与数组相加的整数 II：排序+3次尝试(nlog n)

力扣题目链接：https://leetcode.cn/problems/find-the-integer-added-to-array-ii/

给你两个整数数组 nums1 和 nums2。

从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。

返回能够实现数组相等的 最小 整数 x 。

示例 1:

输出：-2

解释：

移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。

示例 2:

输出：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 相等。

解题方法：排序+3次尝试

分别对两个数组排序。因为一定有解，所以nums1中前3个元素至少有一个和nums2[0]对应。也就是说，可能的x最多有3种情况。对于每种情况，我们从大到小尝试，如果当前x可行，则返回。

怎么判定nums1删除两个元素后是否每个元素加上x后都和nums2对应呢？只需要两个指针分别指向两个数组中的元素。

在指针没有超出数组有效范围时：

• 若$nums1[n1]+x==nums2[n2]$，则两个指针分别后移
• 否则跳过nums1中的这个数：n1后移n2不动，“跳过次数”加一。（若跳过次数大于2则说明这个x不可行）

最终如果n2指到nums2的末尾，则说明这个x可行。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(\log n)$

AC代码

C++

class Solution {
private:
    bool isOk(vector<int>& nums1, vector<int>& nums2, int x) {
        int skip = 0;
        int n1 = 0, n2 = 0;
        while (n1 < nums1.size() && n2 < nums2.size()) {
            if (nums1[n1] + x == nums2[n2]) {
                n1++, n2++;
            }
            else {
                n1++, skip++;
                if (skip > 2) {
                    return false;
                }
            }
        }
        return n2 == nums2.size();
    }
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--) {
            if (isOk(nums1, nums2, nums2[0] - nums1[i])) {
                return nums2[0] - nums1[i];
            }
        }
        return -1;  // Fake Return
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141072842