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

博主： zhaojun
发布时间：2024 年 08 月 09 日
487 次浏览
暂无评论
650字数
分类：默认分类

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 即可。

<br>

这里面有一些细节可以优化：
- 我们 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。

## 代码
```java
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;
    }
}
```

最后修改：2024 年 10 月 08 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

快帆云
你好，我们的机场：快帆云，已经稳定运营三年多，现在诚邀推广员。...
在nginx层面给任意项目站点增加访问限制：casdoor+oauth2-proxy - Blog By chenchen.site
[...]如果是宝塔用户可以直接使用以下方法安装模块，参考文章...
大概
你好，我就想整一个网盘，用作知识付费，就是普通用户只可以看到标...
zhao
测试
知名1842
表评论1842

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

zhaojun • 2024 年 08 月 09 日

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

**提示：**

## 思路

<br>

## 代码
```java
class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

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

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

return 0;
    }
}
```

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

Spring 使用事件监听来解耦代码

leetcode 3152. 特殊数组 II

2. MySQL 主从搭建 —— 查看同步状态

leetcode 392 判断子序列

Shiro 学习 02 - 授权

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

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款