跳转至

4062. 成对操作转化数组

难度中等

题目描述

给你两个整数数组 source 和 target。

在一次 操作 中，你可以选择 source 中两个 不同 的下标 i 和 j，以及任何整数 delta。然后按如下方式更新 source：

  • source[i] = source[i] + source[j] - delta
  • source[j] = delta

如果在执行该操作 任意 次（包括零次）后能够使 source 等于 target，则返回 true。否则，返回 false。

 

示例 1：

输入： source = [1,2,3], target = [0,2,4]

输出： true

解释：

  • 选择下标 i = 0 和 j = 2，并设置 delta = 4。
  • 操作前，source[0] = 1 且 source[2] = 3。
  • 操作后，
    • source[0] = 1 + 3 - 4 = 0
    • source[2] = 4
  • 因此，source 变为 [0, 2, 4]，这与 target 相等。
  • 因此，答案为 true。

示例 2：

输入： source = [-5,-5], target = [-15,5]

输出： true

解释：

  • 选择下标 i = 1 和 j = 0，并设置 delta = -15。
  • 操作前，source[1] = -5 且 source[0] = -5。
  • 操作后，
    • source[1] = -5 + (-5) - (-15) = 5
    • source[0] = -15
  • 因此，source 变为 [-15, 5]，这与 target 相等。
  • 因此，答案为 true。

示例 3：

输入： source = [1,2,1], target = [0,2,5]

输出： false

解释：

可以证明，无论执行什么操作，都无法使 source 等于 target。因此，答案为 false。

 

提示：

  • 2 <= source.length == target.length <= 105
  • -109 <= source[i], target[i] <= 109

解法

方法一：判断数组和

思考

数组长度可以到 \(10^5\)，枚举操作序列无法在时限内完成。一次操作把 \(\textit{source}[j]\) 改成任意整数 \(\textit{delta}\)，同时让 \(\textit{source}[i]\) 增加 \(\textit{source}[j]-\textit{delta}\)。两个位置的和不变，整个数组的和也就不变。

\(n\ge 2\) 时，和相等已经足够。固定最后一个位置做配合，从左到右把前 \(n-1\) 个位置改成 \(\textit{target}\) 的对应值，总和不变会迫使最后一项变成 \(\textit{target}[n-1]\)。

因此只要比较两个数组的和。元素绝对值不超过 \(10^9\)，长度不超过 \(10^5\)，和要用 \(64\) 位整数。

一次操作选择不同下标 \(i\)、 \(j\) 和整数 \(\textit{delta}\)，把 \(\textit{source}[i]\) 更新为 \(\textit{source}[i]+\textit{source}[j]-\textit{delta}\)，把 \(\textit{source}[j]\) 更新为 \(\textit{delta}\)。这两个位置的新和仍是原来的和，数组总和不变。总和不同时无法转化。

总和相同时一定可以转化。下标 \(n-1\) 始终作为配合位置。对 \(i=0,1,\ldots,n-2\)，取

\[ \textit{delta}=\textit{source}[i]+\textit{source}[n-1]-\textit{target}[i], \]

操作后 \(\textit{source}[i]=\textit{target}[i]\)。前 \(n-1\) 项与 \(\textit{target}\) 对齐之后，两边总和相等，最后一项必然等于 \(\textit{target}[n-1]\)。

累加时使用 \(64\) 位整数。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

1
2
3
class Solution:
    def canTransform(self, source: list[int], target: list[int]) -> bool:
        return sum(source) == sum(target)

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean canTransform(int[] source, int[] target) {
        long d = 0;
        for (int i = 0; i < source.length; ++i) {
            d += source[i] - target[i];
        }
        return d == 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool canTransform(vector<int>& source, vector<int>& target) {
        long long s = 0;
        for (int x : source) {
            s += x;
        }
        for (int x : target) {
            s -= x;
        }
        return s == 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func canTransform(source []int, target []int) bool {
    var s, t int64
    for _, x := range source {
        s += int64(x)
    }
    for _, x := range target {
        t += int64(x)
    }
    return s == t
}

1
2
3
4
5
function canTransform(source: number[], target: number[]): boolean {
    return (
        source.reduce((s, x) => s + BigInt(x), 0n) === target.reduce((s, x) => s + BigInt(x), 0n)
    );
}

评论