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

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

这是我的probem代码：

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