leetcode 3132. 找出与数组相加的整数 II

https://leetcode.cn/problems/find-the-integer-added-to-array-ii/description/

题目

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

思路

先将 $nums1$ 和 $nums2$ 升序排序，根据题意 $num1$ 中只有 2 个多余的值，其余的值依次(因为我们排过序了)和 $nums2$ 中的值差值一样。 既然只有 2 个多余值，那么 $nums1[0], num1[1], num1[2]$ 中肯定至少有一个是正确差值, 标记这个下标为 k(即 k 依次等于 0,1,2)，将 $nums1[k]$ 与 $nums2[0]$ 的差值假定为正确差值 $diff$，然后依次比较之后的元素，即从 $num1[k + 1], nums2[1]$ 开始比较差值如等于 $diff$ 则 $count + 1$, 直到遍历完整个数组，等于 $diff$ 的数量为 $nums2.length$，表示我们假定的差值是对的。

具体逻辑为用双指针 $x = k + 1, y = 1$，$x$ 是 $nums1$ 的下标，$y$ 是 $nums2$ 的下标, $count$ 基础值为 1 (假定那个值是对的)：

• 如果 $nums1[x] - num2[y] == diff$，则 count + 1，然后将 x, y 都向后移动一位继续比较。
• 如果 $nums2[x] - num2[y] != diff$，这时可能 x 是多余的值，只将 x 向后移动一位继续比较。
• 直到 x 达到 nums1 的末尾或 y 到了 nums2 的末尾，判断 count 是否 nums2 的长度，是的话返回假定的正确差值 diff 即可。

这里面有一些细节可以优化：

• 我们 count 初始值是 1，y 初始值也是 1，都是差值等于 diff 时才 +1，那我们就不用声明 count 了，直接用 y 即可。
• 如果 x 和 y 的距离大于了 2，那就说明碰到了不止 2 个多余的值，这说明我们假定的 diff 是错的，可以直接停止循环，用下个假定的 diff 继续找。

还有一个要注意的是，我们要先将 k = 2，再 = 1，再 = 0，因为题意要找的是最小的差值，而我们是按升序排序的，靠后的下标值越大，相较与 nums1 的差值也就越小。如 nums1 = [3,3,5,5], num2 = [7,7] 这种情况，如果我们 k 从 0 开始的话，找到的结果就是 4，其实答案应该是 2。

代码

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int m = nums1.length;
        int n = nums2.length;

        for (int k = 2; k >= 0; k--) {
            int diff = nums2[0] - nums1[k];
            int x = k + 1, y = 1;
            while(x < m && y < n && x - y <= 2) {
                if (nums2[y] - nums1[x] == diff) {
                    y++;
                }
                x++;
            }

            if (y == n) {
                return diff;
            }
        }

        return 0;
    }
}