14.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。

思路

注意是子数组，不能全排序
如果按照题目中的做，应该每个子数组排序，判断是否可整合，那么时间复杂度是o(n*n*log(n)*n)
但是仔细观察，可整合数组有两个规律

• 无重合数字
• 最大值 - 最小值 + 1 = 子数组长度

因此只要遍历所有n*n个子数组，找到满足以上规律的结合即可

代码

public static int getLen(int[] a){
	HashSet<Integer> set = new HashSet<Integer>();
	int min = 0;
	int max = 0;
	int len = 0;
	for(int i = 0; i < a.length; i++){
		//遍历结束以i开头的子数组，要清空
		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;
		for(int j = i; j < a.length; j++){
			//重复，后面的子数组也会重复
			if(set.contains(a[j])){
				break;
			}
			set.add(a[j]);
			max = Math.max(max, a[j]);
			min = Math.min(min, a[j]);
			//最大值 - 最小值 + 1 = 子数组长度 = j-i+1
			if(j - i == max - min){
				len = Math.max(len, j - i + 1);
			}
		}
		//遍历结束以i开头的子数组，要清空
		set.clear();
	}
	return len;
}