题目描述
给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：
- 选择两个下标
i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k 。
如果对于所有满足 0 <= i < n 都有 num1[i] == nums2[i] ，那么我们称 nums1 等于 nums2 。
请你返回使 nums1 等于 nums2 的 最少 操作数。如果没办法让它们相等，请你返回 -1 。
示例 1：
输入：nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
输出：2
解释：我们可以通过 2 个操作将 nums1 变成 nums2 。
第 1 个操作：i = 2 ，j = 0 。操作后得到 nums1 = [1,3,4,4] 。
第 2 个操作：i = 2 ，j = 3 。操作后得到 nums1 = [1,3,7,1] 。
无法用更少操作使两个数组相等。
示例 2：
输入：nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
输出：-1
解释：无法使两个数组相等。
提示：
n == nums1.length == nums2.length2 <= n <= 1050 <= nums1[i], nums2[j] <= 1090 <= k <= 105
解法
方法一：一次遍历
我们用两个变量 \(a\) 和 \(b\) 分别记录将 \(\textit{nums1}\) 中的元素增加 \(k\) 和减少 \(k\) 的次数。
我们遍历两个数组，如果两个指针指向的元素相等，则继续；如果两个指针指向的元素不相等，则如果 \(k\) 等于 \(0\) 或者两个元素之差不能被 \(k\) 整除，则返回 \(-1\)；否则将两个元素之差除以 \(k\) 得到操作数 \(t\)，如果 \(t\) 小于 \(0\)，则将 \(-t\) 加到 \(a\) 上，否则将 \(t\) 加到 \(b\) 上。
最后如果 \(a\) 和 \(b\) 相等，则返回 \(a\)，否则返回 \(-1\)。
时间复杂度 \(O(n)\)，其中 \(n\) 是两个数组的长度。空间复杂度 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
a = b = 0
for x, y in zip(nums1, nums2):
if x == y:
continue
if k == 0 or (x - y) % k:
return -1
t = (x - y) // k
if t < 0:
a += -t
else:
b += t
return a if a == b else -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public long minOperations(int[] nums1, int[] nums2, int k) {
long a = 0, b = 0;
for (int i = 0; i < nums1.length; ++i) {
int x = nums1[i], y = nums2[i];
if (x == y) {
continue;
}
if (k == 0 || (x - y) % k != 0) {
return -1;
}
int t = (x - y) / k;
if (t < 0) {
a += -t;
} else {
b += t;
}
}
return a == b ? a : -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
long long minOperations(vector<int>& nums1, vector<int>& nums2, int k) {
long long a = 0, b = 0;
for (int i = 0; i < nums1.size(); ++i) {
int x = nums1[i], y = nums2[i];
if (x == y) {
continue;
}
if (k == 0 || (x - y) % k != 0) {
return -1;
}
int t = (x - y) / k;
if (t < 0) {
a += -t;
} else {
b += t;
}
}
return a == b ? a : -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func minOperations(nums1 []int, nums2 []int, k int) int64 {
var a, b int64
for i, x := range nums1 {
y := nums2[i]
if x == y {
continue
}
if k == 0 || (x-y)%k != 0 {
return -1
}
t := (x - y) / k
if t < 0 {
a += int64(-t)
} else {
b += int64(t)
}
}
if a == b {
return a
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function minOperations(nums1: number[], nums2: number[], k: number): number {
let [a, b] = [0, 0];
for (let i = 0; i < nums1.length; ++i) {
const [x, y] = [nums1[i], nums2[i]];
if (x === y) {
continue;
}
if (k === 0 || (x - y) % k !== 0) {
return -1;
}
const t = (x - y) / k;
if (t < 0) {
a += -t;
} else {
b += t;
}
}
return a === b ? a : -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | impl Solution {
pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
let mut a: i64 = 0;
let mut b: i64 = 0;
for (&x, &y) in nums1.iter().zip(nums2.iter()) {
if x == y {
continue;
}
if k == 0 || (x - y) % k != 0 {
return -1;
}
let t = (x - y) / k;
if t < 0 {
a += (-t) as i64;
} else {
b += t as i64;
}
}
if a == b {
a
} else {
-1
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | long long minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
long long a = 0, b = 0;
for (int i = 0; i < nums1Size; ++i) {
int x = nums1[i], y = nums2[i];
if (x == y) {
continue;
}
if (k == 0 || (x - y) % k != 0) {
return -1;
}
int t = (x - y) / k;
if (t < 0) {
a += -t;
} else {
b += t;
}
}
return a == b ? a : -1;
}
|