題目敘述 Make Two Arrays Equal by Reversing Subarrays
題目給定兩個輸入陣列，請問能否透過子陣列的反轉讓兩個陣列相等?
子陣列的反轉操作次數不受限制。如果可以，返回True
如果不行，返回False
測試範例
Example 1:
Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation:
反轉 2, 4, 1 -> 變成 1, 4, 2
arr=[1,4,2,3]
反轉 4, 2 -> 變成 2, 4
arr=[1,2,4,3]
反轉 4, 3-> 變成 3, 4
arr=[1,2,3,4]
這時候達成目標，兩個陣列相等，都是[1,2,3,4]
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
兩個陣列target, arr的長度一定相同。
1 <= target.length <= 1000
陣列長度介於1~1000之間。
1 <= target[i] <= 1000
target陣列的每個元素介於1~1000之間。
1 <= arr[i] <= 1000
arr陣列的每個元素介於1~1000之間。
演算法 字典統計出現的數字和出現次數
因為反轉只會影響位置，所以如果要讓反轉之後的陣列有機會相同的話，必須額外滿足兩格條件:
- 出現的數字相同，你有我也有。
- 而且數字的出現次數也要相同，例如1都是出現兩次，5都是出現九次,....等等
用字典統計出現的數字和出現次數，如果都完全一樣，才代表兩個陣列有機會在反轉後得到相同的結果。
程式碼 字典統計出現的數字和出現次數
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
target_num_occ_dict = {}
source_num_occ_dict = {}
for num in target:
target_num_occ_dict[num] = target_num_occ_dict.get( num, 0 ) + 1
for num in arr:
source_num_occ_dict[num] = source_num_occ_dict.get( num, 0 ) + 1
return target_num_occ_dict == source_num_occ_dict
複雜度分析
時間複雜度: O(n)
線性掃描每個陣列元素，並且統計出現次數。
空間複雜度: O(n)
需要一個字典去記錄每個陣列元素的出現次數。
