在数组的所有滑动窗口排列中寻找不平衡

Question

我有一个编码问题，我无法完成

给定一个阵列，找到长度为1 <= k <= len(arr)的所有子阵列，并在这些子阵列中找到不平衡

不平衡是指排序数组中两个相邻项目之间的差异超过一个

不平衡定义为与前一个项目相差超过1的项目j的数量，即sorted_arr[j] - sorted_arr[j - 1 > 1

例如给定的数组=[4，1，3，2]

子阵列为：

1. [4]
2. [1]
3. [3]
4. [2]
5. [4, 1]
6. [1, 3]
7. [3, 2]
8. [4, 1, 3]
9. [1, 3, 2]
10. [4, 1, 3, 2]

对于每个子阵列，在对它们进行排序后，只有5, 6 and 8具有subarray[i] - subarray[i - 1] > 1的情况，在这种情况下，不平衡将增加1

在上面的例子中，imbalance = 3

这是我的问题代码：

def get_imbalance(arr):
imbalance = 0
for i in range(1, len(arr)):
imbalance += 1 if arr[i] - arr[i - 1] > 1 else 0
return imbalance
def func(arr):
imbalance = 0
if len(arr) <= 1: return 0
if len(arr) == 2:
return 1 if abs(arr[0] - arr[1]) > 1 else 0
for i in range(2, len(arr) + 1):
for j in range(len(arr) - i + 1):
imbalance += get_imbalance(sorted(rank[j: j + i]))
return imbalance

我使用一个滑动窗口来获得主数组的所有不同子数组，然后对结果进行排序并返回不平衡。然而，这会遇到超时问题。如何优化算法？

Answer 1

在此处找到解决方案：总体时间复杂度为O(N^2(https://leetcode.com/discuss/interview-question/2461490/Amazon-OA-or-Group-Imbalance-or-2022/1592718