本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode3132. 找出与数组相加的整数 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的最小值未删除。x = nums2的最小值 -nums1的最小值。
二，nums1的最小值被删除，x = nums2的最小值-nums1的次小值。
三，nums1的最小值、次要值被删除。x=nums2的最小值-nums1的第三小值。
确定x后，枚举nums2的值，看nums2[i]-x是否都存在，如果任意值不存在，则失败。如果存在，需要标记或删除。
可以用多键集合实现，找到就删除。
也可以排序后，用双指针实现。
nums1[i]和nums2[j]比较。
显然第三种情况x最小，第二种情况次之，故按三二一开始测试。
时间复杂度：O(nlogn)

代码

核心代码

class Solution {
		public:
			int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
				sort(nums1.begin(), nums1.end());
				sort(nums2.begin(), nums2.end());
				auto Do = [&](int x) {
					int i = 0, j = 0;
					for (int j = 0,i=0; j < nums2.size(); j++) {
						while ((i < nums1.size()) && (nums1[i]+x != nums2[j])) {
							i++;
						}
						i++;
						if (i > nums1.size()) { return false; }
					}
					return true;
				};
				if (Do(nums2[0] - nums1[2])) { return nums2[0] - nums1[2]; }
				if (Do(nums2[0] - nums1[1])) { return nums2[0] - nums1[1]; }
				return nums2[0] - nums1[0];
			}
		};

单元测试

vector<int> nums1,nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 4, 20, 16, 12, 8 }, nums2 = { 14, 18, 10 };
			auto res = Solution().minimumAddedInteger(nums1, nums2);
			AssertEx(-2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 3,5,5,3 }, nums2 = { 7,7 };
			auto res = Solution().minimumAddedInteger(nums1, nums2);
			AssertEx(2, res);
		}