【搞定算法】最长的可整合子数组的长度

冷不防 2021-11-23 01:20 228阅读 0赞

> **题目：最长的可整合子数组的长度。给定一个整型数组 arr，请返回其中最大可整合子数组的长度**。例如：\[5,5,3,2,6,4,3\] 的最大可整合子数组为\[5,3,2,6,4\]，所以返回 5。
> 
> 先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数差的绝对值都为 1，则该数组为可整合数组。例如：\[5,3,4,6,2\] 排序之后为 \[2,3,4,5,6\]，符合每相邻两个数差的绝对值都为 1，所以这个数组为可整合数组。

** 分析：**

**1、暴力：**

列出所有的子数组【N^2】,然后再对每个子数组复制，再排序（N*logN）,再遍历看满不满足，共 O(N^3*logN) 【子数组：数组中一个或连续的多个整数组成一个子数组】；

**2、优化：**

以后看到复杂的标准先自己改为简洁的标准。新的标准：一个数组如果是可整合的：

**1）无重复值；**

**2）最大值减去最小值等于数组个数减 1 的话，则是可整合的。**

则尝试所有的子数组的复杂度为 O(N^2)，判断每个子数组是否是可整合的复杂度为 O(1)（遍历时只需要记录 min、max 就可以判断是否时可整合数组了）。

public class LongestIntegrationLength {
    
        public static int getLongest(int[] arr){
            if(arr == null || arr.length == 0){
                return 0;
            }
    
            int maxLen = 0;
            HashSet<Integer> set = new HashSet<>();
            // 尝试以每个 i 开头的子数组
            for(int i = 0; i < arr.length; i++){
                int max = Integer.MIN_VALUE;
                int min = Integer.MAX_VALUE;
                for(int j = i; j < arr.length; j++){
                    if(set.contains(arr[j])){
                        // 如果包含重复数字，则直接进行一下位作为数组的开头
                        break;
                    }
                    set.add(arr[j]);
                    max = Math.max(max, arr[j]);
                    min = Math.min(min, arr[j]);
                    // 数组的个数为：j - i + 1，再减去1，即为：j - i
                    if(max - min == j - i){
                        // 最大减最小等于当前数组的长度，说明每个数字之间的跨度都是1，可以整合
                        maxLen = Math.max(maxLen, j - i + 1);
                    }
                }
                // 每次以一个新的数字作为子数组开头的时候，都要先清空set
                set.clear();
            }
            return maxLen;
        }
    
        public static void main(String[] args) {
            int[] arr = { 5, 5, 3, 2, 6, 4, 3 };  // 5, 3, 2, 6, 4
            System.out.println(getLongest(arr));  // 5
        }
    }