LeetCode 题解工作台
找出与数组相加的整数 II
给你两个整数数组 nums1 和 nums2 。 从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。 执行上述操作后， nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们首先对数组 和 进行排序，由于我们需要从 中移除两个元素，因此我们只需要考虑 的前三个元素，分别记为 $a_1, a_2, a_3$，我们可以枚举 的第一个元素 ，那么我们可以得到 $x = b_1 - a_i$，其中 $i \in \{1, 2, 3\}$。然后我们可以通过双指针的方法来判断是否存在一个整数 ，使得 和 相等，取满足条件的最小的 即可。 时间复杂度 $O(n …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个整数数组 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相等。
解题思路
方法一：排序 + 枚举 + 双指针
我们首先对数组 和 进行排序，由于我们需要从 中移除两个元素，因此我们只需要考虑 的前三个元素，分别记为 ，我们可以枚举 的第一个元素 ，那么我们可以得到 ，其中 。然后我们可以通过双指针的方法来判断是否存在一个整数 ，使得 和 相等，取满足条件的最小的 即可。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
def f(x: int) -> bool:
i = j = cnt = 0
while i < len(nums1) and j < len(nums2):
if nums2[j] - nums1[i] != x:
cnt += 1
else:
j += 1
i += 1
return cnt <= 2
nums1.sort()
nums2.sort()
ans = inf
for i in range(3):
x = nums2[0] - nums1[i]
if f(x):
ans = min(ans, x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the removal process by efficiently handling the two-element removal?
- question_mark
Does the candidate consider both removal strategies and invariant tracking?
- question_mark
How does the candidate handle edge cases like multiple equal elements in nums1 and nums2?
常见陷阱
外企场景- error
Failing to consider all possibilities of element removal and assuming the answer from a single scenario.
- error
Not correctly updating the value of x after adjusting for the removed elements.
- error
Misunderstanding the conditions under which nums1 is transformed into nums2, leading to incorrect assumptions about element removal.
进阶变体
外企场景- arrow_right_alt
Variation in array size or element values, adjusting complexity for larger or smaller arrays.
- arrow_right_alt
Changes to the number of elements removed from nums1, modifying the number of potential scenarios to consider.
- arrow_right_alt
Introducing additional constraints that may change the solution's approach, such as allowing for negative values in nums1 and nums2.