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

题目描述：

给你两个整数数组 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 排序，在nums1中删除两个元素后，就会有三种情况：nums1的第一个元素为nums[0]、nums[1]、nums[2]

那么，只需要枚举这三种情况，判断删除后的nums1和nums2每个元素的差值是否相等，就可以得出这种情况是否满足题意

当从下标i开始遍历，遍历完整个数组后：

• 如果在nums1里面找到length(nums2)个元素相等，说明从下标i开始删除两个元素后，nums1和nums2每个元素的差值都相等，此时nums2[0] - nums1[i]可以作为结果参考之一。
• 否则，则不作为参考结果

为了获得最小值，需要遍历三种情况，最终取最小值即可。

import "sort"

func minimumAddedInteger(nums1 []int, nums2 []int) int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	var result = nums2[0] - nums1[0]
	for i := 0; i <= 2; i++ {
		left, right := i+1, 1
		for left < len(nums1) && right < len(nums2) {
			if nums1[left]-nums2[right] == nums1[i]-nums2[0] {
				right++
			}
			left++
		}
		if right == len(nums2) && result > nums2[0]-nums1[i] {
			result = nums2[0] - nums1[i]
		}
	}
	return result
}

复杂度：

• 时间复杂度：O(n * log n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.7 MB,击败了63.64% 的Go用户