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

解题思路

解题思路

这道题的关键观察是：通过翻转子数组，我们可以实现数组元素的任意重新排列。

核心洞察：

  • 翻转操作可以改变数组中元素的相对位置
  • 通过多次翻转不同的子数组，理论上可以将数组重新排列成任意顺序
  • 因此，只要两个数组包含相同的元素（元素种类和数量完全一致），就一定可以通过翻转操作使它们相等

解法分析：

  1. 排序比较法（推荐）：将两个数组分别排序，然后比较是否完全相同。如果排序后相等，说明两数组包含相同的元素集合。

  2. 哈希表计数法：统计两个数组中每个元素的出现次数，比较计数是否相同。

  3. 直接比较法：由于数据范围较小，可以用数组代替哈希表进行计数。

排序法最简洁直观，时间复杂度为 O(n log n)，适合此题的数据规模。虽然计数法能达到 O(n) 时间复杂度，但在实际应用中，由于 n 较小且排序常数较小，排序法通常表现更好。

代码实现

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        sort(target.begin(), target.end());
        sort(arr.begin(), arr.end());
        return target == arr;
    }
};

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

public class Solution {
    public bool CanBeEqual(int[] target, int[] arr) {
        Array.Sort(target);
        Array.Sort(arr);
        return target.SequenceEqual(arr);
    }
}

var canBeEqual = function(target, arr) {
    if (target.length !== arr.length) return false;
    
    const targetCount = {};
    const arrCount = {};
    
    for (let i = 0; i < target.length; i++) {
        targetCount[target[i]] = (targetCount[target[i]] || 0) + 1;
        arrCount[arr[i]] = (arrCount[arr[i]] || 0) + 1;
    }
    
    for (let key in targetCount) {
        if (targetCount[key] !== arrCount[key]) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(1)原地排序，不需要额外空间