2023-07-27：最长可整合子数组的长度， 数组中的数字排序之后，相邻两数的差值是1， 这种数组就叫可整合数组。 给定一个数

2023-07-27：最长可整合子数组的长度，

数组中的数字排序之后，相邻两数的差值是1，

这种数组就叫可整合数组。

给定一个数组，求最长可整合子数组的长度。

答案2023-07-27：

算法maxLen的过程如下：

1.检查输入数组是否为空，如果为空，则返回0，表示最长可整合子数组长度为0。

2.初始化长度为1的最长可整合子数组长度为ans。

3.创建一个空的set容器，用于记录数组中的元素是否已经存在。

4.开始遍历输入数组，从start = 0开始。每次迭代，重置set为空。

5.初始化minVal和maxVal为arr[start]。

6.将arr[start]添加到set中，表示该元素已经存在。

7.开始从start+1位置向后遍历数组，每次迭代的终止条件是end < len(arr)。

8.如果arr[end]在set中已经存在，表示遇到了重复元素，跳出循环。

9.将arr[end]添加到set中，表示该元素已经存在。

10.更新minVal和maxVal，如果arr[end]比minVal小，则更新minVal为arr[end]；如果arr[end]比maxVal大，则更新maxVal为arr[end]。

11.检查当前子数组是否为可整合数组，即判断maxVal和minVal之间的差值是否等于end-start。

12.如果当前子数组为可整合数组，更新ans为当前子数组长度和ans中较大的值。

13.返回最长可整合子数组长度ans。

算法right的过程如下：

1.检查输入数组是否为空，如果为空，则返回0，表示最长可整合子数组长度为0。

2.初始化ans为0，用于记录最长可整合子数组的长度。

3.创建一个和输入数组相同长度的辅助数组help。

4.开始从左边界l开始遍历数组，每次迭代，右边界r从l开始向右遍历数组。

5.将arr[l:r+1]拷贝到辅助数组help的对应位置。

6.对help数组的切片help[l:r+1]进行排序，将切片中的元素按从小到大的顺序排列。

7.检查排序后的help数组是否符合可整合数组的条件，即判断help数组中相邻元素之间的差值是否为1。

8.如果help数组满足可整合数组条件，更新ans为当前子数组长度和ans中较大的值。

9.返回最长可整合子数组长度ans。

算法maxLen的时间复杂度和空间复杂度分别为：

时间复杂度：

• 最坏情况下，需要遍历输入数组中的每个元素，所以时间复杂度为O(n)，其中n是输入数组的长度。

空间复杂度：

• 使用了一个set容器来存储元素，所以空间复杂度为O(n)，其中n是输入数组的长度。

算法right的时间复杂度和空间复杂度分别为：

时间复杂度：

• 最坏情况下，需要对每个子数组进行排序，对于长度为m的子数组，排序的时间复杂度为O(mlogm)。

• 因此，整个算法的时间复杂度为O(n^2 log n)，其中n是输入数组的长度。

空间复杂度：

• 使用了一个辅助数组help存储子数组的拷贝，所以空间复杂度为O(n)，其中n是输入数组的长度。

go完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述