题目描述:
给你两个整数数组 nums1
和 nums2
。
从 nums1
中移除两个元素,并且所有其他元素都与变量 x
所表示的整数相加。如果 x
为负数,则表现为元素值的减少。
执行上述操作后,nums1
和 nums2
相等 。当两个数组中包含相同的整数,并且这些整数出现的频次相同时,两个数组 相等 。
返回能够实现数组相等的 最小 整数 x
输入输出实例:
思路:我们先对两个列表元素进行排序,这样更便于我们找到x,题目中要求我们在nums1中删除两个元素后都加x才能与nums2匹配,那么我们可以确定,我们在nums1中找三个元素,那么这三个元素肯定至少有一个是满足不被删除的,既然它不用被删除,那他与nums2中对应元素相减得到的就可能是我们的x。为了方便我们可以选用前三个元素,也就是nums1[2],nums1[1],nums1[0]中至少有一个满足条件,这里我们遍历的时候从高往低遍历,因为题目要我们找最小的x(如果nums1=[1,2,3],nums2=[4],用这个例子可以直观的看出来我们的x是4-3=1),这三个元素中肯定有一个对应的是nums2[0],所以nums2[0]-nums1[i]一定有一个是我们的x。然后我们用双指针,第一个指针n1起始位置在nums1[i+1],第二个指针n2起始位置在nums2[1],然后我们找n2所指的元素减去n1所指的元素和nums2[0]-nums1[i]比,如果不同,那么我们第一个指针往右走,如果相同我们两个指针都往右走,直到有一个指针走完列表,如果最后第二个指针走到了最后,那么说明这个时候的nums2[0]-nums1[i]就是我们要找的x。(如果觉得还是有点难以理解,可以跟着上诉思路对着实例自己画图做一做,会清晰很多)根据上述思路有以下代码:
class Solution:def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:#对nums1和nums2两个列表进行排序nums1.sort()nums2.sort()m,n = len(nums1),len(nums2)#既然要移除两个元素,那么我们找nums1三个元素,这三个元素里面肯定至少有一个是被保留的#我们可以找前三个或者是后三个,需要注意的是题目要我们找最小的整数x,为了保证最小,我们找的三个元素顺序是从大往小遍历for i in [2,1,0]:#采用双指针,从i+1,1开始是因为我们要用第i(nums1),0(nums2)这些元素用来做找到x的标准n1,n2 = i+1,1while n1 < m and n2 < n :#判断第i个是否满足被保留if nums2[0] - nums1[i] == nums2[n2] - nums1[n1]:n2 += 1n1 += 1#n2=n的时候我们找完if n2 == n :return nums2[0] - nums1[i]