1460.md

title	description	keywords
1460. 通过翻转子数组使两个数组相等	LeetCode 1460. 通过翻转子数组使两个数组相等题解，Make Two Arrays Equal by Reversing Subarrays，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1460. 通过翻转子数组使两个数组相等 通过翻转子数组使两个数组相等 Make Two Arrays Equal by Reversing Subarrays 解题思路 数组 哈希表 排序

1460. 通过翻转子数组使两个数组相等

🟢 Easy  🔖  数组 哈希表 排序  🔗 力扣 LeetCode

题目

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can makearr equal totarget _ or _false otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]

Output: true

Explanation: You can follow the next steps to convert arr to target:

1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]

2- Reverse subarray [4,2], arr becomes [1,2,4,3]

3- Reverse subarray [4,3], arr becomes [1,2,3,4]

There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]

Output: true

Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]

Output: false

Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

• target.length == arr.length
• 1 <= target.length <= 1000
• 1 <= target[i] <= 1000
• 1 <= arr[i] <= 1000

题目大意

给你两个长度相同的整数数组 target 和 arr 。每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同，返回 true；否则，返回 false 。

示例 1：

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

输出： true

解释： 你可以按照如下步骤使 arr 变成 target：

1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]

2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]

3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]

上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。

示例 2：

输入： target = [7], arr = [7]

输出： true

解释： arr 不需要做任何翻转已经与 target 相等。

示例 3：

输入： target = [3,7,9], arr = [3,7,11]

输出： false

解释： arr 没有数字 9 ，所以无论如何也无法变成 target 。

提示：

• target.length == arr.length
• 1 <= target.length <= 1000
• 1 <= target[i] <= 1000
• 1 <= arr[i] <= 1000

解题思路

问题要求判断是否可以通过任意次数组元素的交换使 arr 转换为 target。这种情况等价于检查两个数组中每个数字出现的次数是否完全相同。

思路一：哈希表

1. 统计 target 中每个数字的频次:

   • 使用一个 Map 来存储数字及其出现的次数。

2. 更新频次:

   • 遍历 arr，对每个数字对应的计数减 1。

3. 验证频次是否平衡:

   • 检查 Map 中所有的值是否都为 0，若不是，则两个数组不能通过交换等价。

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组长度，遍历 target 和 arr。
• 空间复杂度: O(n)，需要存储 Map，占用的空间与数字种类的数量成正比。

---

思路二：排序

也可以通过排序的方式实现同样的效果。

• 对 target 和 arr 分别进行排序。
• 比较排序后的数组转成字符串后，是否相等。

复杂度分析

• 时间复杂度: O(n log n) (排序)
• 空间复杂度: O(1) (排序原地操作)

代码

::: code-tabs @tab 哈希表

/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {boolean}
 */
var canBeEqual = function (target, arr) {
	let count = new Map();
	for (let num of target) {
		count.set(num, (count.get(num) || 0) + 1);
	}

	for (let num of arr) {
		count.set(num, (count.get(num) || 0) - 1);
	}

	for (let value of count.values()) {
		if (value !== 0) return false;
	}
	return true;
};

@tab 排序

var canBeEqual = function (target, arr) {
	target.sort((a, b) => a - b);
	arr.sort((a, b) => a - b);
	return target.join() === arr.join();
};

:::