算法刷题目数组和矩阵
Source
Edit
History

最长的可整合子数组的长度

最长的可整合子数组的长度

一、题目

先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为1，或者该数组长度为1，则该数组为可整合数组。例如，[5, 3, 4, 6, 2]排序后为[2, 3, 4, 5, 6]，符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组

给定一个数组arr, 请返回其中最大可整合子数组的长度。例如，[5, 5, 3, 2, 6, 4, 3]的最大可整合子数组为[5, 3, 2, 6, 4]，所以请返回5

二、思路

我们首先需要获取到这个数组中的所有子数组，然后在判断这个子数组是否为可整合的。判断可整合可以按照这样的思路，这个子数组必须是没有重复元素，并且最大值减去最小值，再加一的结果等于元素的个数。也即：(max - min + 1 == 元素个数)。那么这个子数组就是可整合数组。

没有重复元素可以使用 set 来做判断

找到这个数组中所有子数组的时间复杂度是 O(N2)，检验是否为可整合的为 O(1)。整体的时间复杂度为 O(N2)。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <vector>
#include <set>
#include <iostream>

class Solution {
public:
    int get_LIL(const std::vector<int>& arr) {
        if (arr.empty()) {
            return 0;
        }
        int res = 0;
        int min = INT32_MAX;
        int max = INT32_MIN;
        std::set<int> st;
        for (int i = 0; i < arr.size(); ++i) {
            for (int j = i; j < arr.size(); ++j) {
                if (st.find(arr[j]) != st.end()) {
                    break;
                }
                st.insert(arr[j]);
                min = std::min(min, arr[j]);
                max = std::max(max, arr[j]);
                if (max - min == j - i) {
                    res = std::max(res, j - i + 1);
                }
            }
            st.clear();
        }
        return res;
    }
};

int main() {
    Solution s;
    std::vector<int> arr{5, 5, 3, 2, 6, 4, 3};
    auto res = s.get_LIL(arr);
    std::cout << res << std::endl;
    return 0;
}