LeetCode 每日一题 1460. 通过翻转子数组使两个数组相等

文章目录

1. 题目2. 描述3. 思路4. 实现

1. 题目

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

2. 描述

给你两个长度相同的整数数组 target 和 arr 。

每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

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

3. 思路

要通过翻转使得两数组相等，那么首先它的长度必相同，所以长度不同都不用比较，一定不行在数组长度相同的情况下，分别对俩数组进行排序遍历排序后的数组，将两者各位置的值进行比较，一旦不同则说明不能通过翻转成功此时的操作做要有排序操作，时间复杂度为 $O(n\ast logn)$ 和遍历操作，时间复杂度为 $O(n)$，所以整体时间复杂度为 $O(n\ast logn)$.

4. 实现

public boolean canBeEqual(int[] target, int[] arr) { // 两数组元素个数都不同，不可能通过翻转相等 if (arr.length != target.length){ return false; } // 将两个数组排序 Arrays.sort(target); Arrays.sort(arr); // 将排序后的数组进行比较，一旦有不同的元素，则说明不能通过翻转相等 for (int i = 0; i < target.length; i++) { if (arr[i]!=target[i]){ return false; } } return true; }