Why does Make Two Arrays Equal by Reversing Subarrays reduce to counting values?

Because reversing subarrays can reorder elements extensively, but it never changes which values exist or how many times each appears. That means the decision depends only on whether target and arr have identical frequencies for every number.

Is sorting a valid solution for this problem?

Yes. If both arrays sort to the same sequence, they contain the same multiset of values, so the answer is true. However, sorting is slower than the direct frequency-count approach.

Why is the primary pattern array scanning plus hash lookup?

You solve the problem by scanning target and arr while updating counts in a hash map or counting array. The hash lookup gives constant-time frequency checks, which directly targets the mismatch condition this problem cares about.

What is the main failure mode to watch for?

The biggest mistake is ignoring duplicates. Two arrays may contain the same distinct numbers but still be impossible to match if one value appears a different number of times.

Can I use a counting array instead of a hash map?

Yes. Since the values are bounded, a counting array works well and keeps the same O(N) time. It is often even cleaner than a hash map for this specific constraint range.

#1460

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你两个长度相同的整数数组 target 和 arr 。每一步中，你可以选择 arr 的任意非空子数组并将它翻转。你可以执行此过程任意次。如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。示例 1：输入： target = [1,2,3,4], ar…

数组哈希表排序

题目描述

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

lightbulb

解题思路

方法一：排序

如果两个数组排序后相等，那么它们可以通过翻转子数组变成相等的数组。

因此，我们只需要对两个数组进行排序，然后判断排序后的数组是否相等即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $arr$ 的长度。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
They want you to stop simulating reversals and explain why order is not the real constraint in this problem.
question_mark
They expect you to notice that every element in target must have a matching occurrence in arr, including duplicates.
question_mark
They may ask why a sorting solution works, then push for the linear-time hash counting version.

warning

常见陷阱

外企场景

error
Comparing elements by index and trying to greedily fix positions, which ignores how powerful repeated subarray reversals are.
error
Checking only set membership instead of frequencies, which breaks on duplicates like target = [1,1,2] and arr = [1,2,2].
error
Using sorting as the main explanation without stating the deeper invariant that this problem depends on: equal multisets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use sorting on both arrays and compare them, which is simpler to code but slower at O(N log N).
arrow_right_alt
Use a fixed-size counting array instead of a hash map because values are bounded, reducing hash overhead for this problem.
arrow_right_alt
Return the first mismatched value count during the scan if an interviewer wants early failure detection rather than only a final boolean check.

help

常见问题

外企场景

继续练习

#1481 不同整数的最少数目 #1418 点菜展示表 #1366 通过投票对团队排名