题目描述
给你两个长度相等的数组 nums1
和 nums2
。
数组 nums1
中的每个元素都与变量 x
所表示的整数相加。如果 x
为负数,则表现为元素值的减少。
在与 x
相加后,nums1
和 nums2
相等 。当两个数组中包含相同的整数,并且这些整数出现的频次相同时,两个数组 相等。
返回整数 x
。
样例
输入:nums1 = [2,6,4], nums2 = [9,7,5]
输出:3
解释:
与 3 相加后,nums1 和 nums2 相等。
输入:nums1 = [10], nums2 = [5]
输出:-5
解释:
与 -5 相加后,nums1 和 nums2 相等。
输入:nums1 = [1,1,1,1], nums2 = [1,1,1,1]
输出:0
解释:
与 0 相加后,nums1 和 nums2 相等。
限制
1 <= nums1.length == nums2.length <= 100
0 <= nums1[i], nums2[i] <= 1000
- 测试用例以这样的方式生成:存在一个整数
x
,使得nums1
中的每个元素都与x
相加后,nums1
与nums2
相等。
算法
(思维题) $O(n)$
- 由于题目保证了
x
一定存在,且两个数组在排序后,nums1
整体加上x
是等于nums2
的,所以x
可以取两个数组中最小元素的差值。
时间复杂度
- 遍历两个数组一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int addedInteger(vector<int>& nums1, vector<int>& nums2) {
const int n = nums1.size();
int ma1 = 0, ma2 = 0;
for (int i = 0; i < n; i++) {
if (nums1[i] > ma1) ma1 = nums1[i];
if (nums2[i] > ma2) ma2 = nums2[i];
}
return ma2 - ma1;
}
};