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

难度: Easy

给你两个长度相同的整数数组 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

Submission

运行时间: 24 ms

内存: 16.2 MB

from typing import List

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(target) == sorted(arr)

Explain

题解的思路是利用排序来检查两个数组是否可以通过翻转子数组来相等。这种方法依赖于一个核心思想：只要两个数组包含相同的元素且各元素的数量相同，那么一个数组总能通过翻转子数组的方式变得与另一个数组相同。通过对两个数组进行排序，如果排序后的数组相等，就意味着它们包含完全相同的元素以及相同的元素数量，因此返回 true，否则返回 false。

时间复杂度: O(n log n)

空间复杂度: O(n)

from typing import List

# 定义一个类名为Solution
class Solution:
    # 函数用于检查通过翻转子数组是否能使两个数组相等
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        # 通过比较排序后的target和arr数组来判断两数组是否可以通过翻转变得相等
        return sorted(target) == sorted(arr)

Explore

选择排序两个数组并比较它们的排序结果是因为，如果两个数组可以通过翻转子数组来相等，那么它们必须具有完全相同的元素以及相同的元素数量。排序是一种有效的方式来验证这一点，因为排序可以使元素以统一的顺序排列，从而简化比较过程。如果排序后的数组相等，这说明两个数组包含相同的元素和数量，因此可以通过翻转子数组来达到相等；如果不等，则无法通过简单的翻转来匹配。

是的，排序后仅比较数组是否相等的方法考虑了数组中元素的重复情况。排序会将数组中的元素按照某种特定顺序排列，如果两个数组包含相同数量的相同元素（包括重复元素），这些元素在排序后的顺序和位置将会完全相同。因此，比较排序后的数组能够准确地反映出两个数组是否具有完全相同的元素，包括它们的重复情况。

在这个具体场景中，使用sorted函数直接返回比较结果是安全的，因为问题的核心是检查两个数组是否包含相同的元素和数量。对于普通的整数数组，排序然后比较是有效且安全的方法。这种方法不受元素类型的影响（只要元素可以被排序），并且没有已知的边界情况会导致错误的比较结果。只要两数组长度相同且元素可排序，排序后的比较就能正确反映两数组是否可以通过翻转子数组变得相同。