数组和矩阵系列算法

1，转圈打印矩阵
题目：给定一个矩阵，请按照转圈打印的方式打印它。
例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

转圈打印结果：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10。
要求：时间复杂度O(1)。
解答：矩阵分圈处理，在矩阵式利用左上角的坐标(tR,tC)和右下角的坐标(dR,dC)就可以表示一个子矩阵，比如，题目中的矩阵，当(tR,tC)=(0,0)、(dR,dC)=(3,3)时，表示的矩阵就是整个矩阵，那么这个字矩阵最外层的部分就是：
1 2 3 4
5 8
9 12
13 14 15 16
这就是当(tR,tC)=(0,0)、(dR,dC)=(3,3)时的子矩阵。接下来令tR和tC加1，即(tR,tC)=(1,1),令dR和dC减1，即(dR,dC)=(2,2),此时表示的子矩阵如下：
6 7
10 11
再转圈打印这个矩阵，tR和tC加1，dR和dC减1，如果发现左上角坐标跑到了右下角坐标的右方或下方，整个过程就停止。
参看如下的代码，spiralOrderPrint方法，其中printEdge就是转圈打印一个子矩阵的外层。

public static void spiralOrderPrint(int[][] matrix) {
	int tR = 0;
	int tC = 0;
	int dR = matrix.length - 1;
	int dC = matrix[0].length - 1;
	while (tR <= dR && tC <= dC) {
		printEdge(matrix, tR++, tC++, dR--, dC--);
	}
}

public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
	if (tR == dR) { 
		for (int i = tC; i <= dC; i++) {
			System.out.print(m[tR][i] + " ");
		}
	} else if (tC == dC) { 
		for (int i = tR; i <= dR; i++) {
			System.out.print(m[i][tC] + " ");
		}
	} else { 
		int curC = tC;
		int curR = tR;
		while (curC != dC) {
			System.out.print(m[tR][curC] + " ");
			curC++;
		}
		while (curR != dR) {
			System.out.print(m[curR][dC] + " ");
			curR++;
		}
		while (curC != tC) {
			System.out.print(m[dR][curC] + " ");
			curC--;
		}
		while (curR != tR) {
			System.out.print(m[curR][tC] + " ");
			curR--;
		}
	}
}

2，将正方形矩阵顺时针转动90度
题目：将一个nn矩阵顺时针转90度，例如
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
顺时针转90度后的矩阵
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
要求：额外空间复杂度为O(1)。
这里仍然使用分圈打印的方式，在矩阵的左上角和右下角的坐标就可以表示一个矩阵，比如，题目中的矩阵，当(tR,tC)=(0,0)、(dR,dC)=(3,3)时，表示的子矩阵就是整个矩阵，那么这个子矩阵最外层的部分如下：
1 2 3 4
5 8
9 12
13 14 15 16
在这个外圈中，1，4，16，13为一组，然后让1占据4的位置，4占据16的位置，16占据13的位置，13占据1的位置，一组就调整完了。然后2，8，15，9，继续占据调整的过程，最后3，12 ，14 ，5为一组，继续占据调整的过程。然后(tC,tC)、(dR,dC)=(3,3)的子矩阵外层就调整完毕。接下来令tR和tC加1，即(tR,tC)=(1,1),令dR和dC减1，即(dR,dC)=(2,2),此时表示的矩阵如下
6 7
10 11
这个外层只有一组，就是6，7，10，11，占据调整之后即可，所以如果子矩阵的大小是mm，一共就有m-1组，分别进行占据调整即可。
请参考如下代码中的rotate方法。

static void rotate(int[][] matrix) {

	int tR = 0;
	int tC = 0;
	int dR = matrix.length - 1;
	int dC = matrix[0].length - 1;
	while (tR < dR) {
		rotateEdge(matrix, tR++, tC++, dR--, dC--);
	}
}

public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {
	int times = dC - tC; 
	int tmp = 0;
	for (int i = 0; i != times; i++) { 
		tmp = m[tR][tC + i];
		m[tR][tC + i] = m[dR - i][tC];
		m[dR - i][tC] = m[dR][dC - i];
		m[dR][dC - i] = m[tR + i][dC];
		m[tR + i][dC] = tmp;
	}
}

3，“之”字型打印矩阵
题目：给定一个矩阵，按照“之”字型打印矩阵，例如:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
“之”字型打印矩阵的结果为：1，2，5，9，6，3，4，7，10，13，14，11，8，12，15，16。

   public static void printMatrixZigZag(int[][] matrix) {
	int tR = 0;
	int tC = 0;
	int dR = 0;
	int dC = 0;
	int endR = matrix.length - 1;
	int endC = matrix[0].length - 1;
	boolean fromUp = false;
	while (tR != endR + 1) {
		printLevel(matrix, tR, tC, dR, dC, fromUp);
		tR = tC == endC ? tR + 1 : tR;
		tC = tC == endC ? tC : tC + 1;
		dC = dR == endR ? dC + 1 : dC;
		dR = dR == endR ? dR : dR + 1;
		fromUp = !fromUp;
	}
	System.out.println();
}

public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
		boolean f) {
	if (f) {
		while (tR != dR + 1) {
			System.out.print(m[tR++][tC--] + " ");
		}
	} else {
		while (dR != tR - 1) {
			System.out.print(m[dR--][dC++] + " ");
		}
	}
}

4，找到无序数组中最小的k个数
题目：给定一个无序的整型数组arr，找到其中最小的k个数。
要求：数组长度为n，排序之后自然可以得到最小的k个数，此时时间复杂度与排序的时间复杂度相同，均为O(logn)。本体要求读者实现时间复杂度为O(nlogk)和O(n)的方法。
O(nlogk)时间复杂度的方法：用堆结构解决，已知维护一个有k个元素的大根堆，这个堆代表目前选出的k个最小的数，在堆里的k个元素中堆顶的元素是最小的k个数里最大的那个。接下里遍历数组，遍历的过程中看当前数是否比堆定元素小，若是，就把堆顶的元素替换成当前的数，然后从堆定的位置调整整个堆，让替换操作后的最大元素继续处在堆定的位置；若不是，则不进行任何操作，继续遍历下一个数；在遍历完成后，堆中的k个数就是所有数组中最小的k个数。
参看下面的getMinKNumsByHeap方法，代码中的heapinsert和heapfy方法分别为堆排序中的建堆和调整堆的实现。

// O(N*logK)
	public static int[] getMinKNumsByHeap(int[] arr, int k) {
		if (k < 1 || k > arr.length) {
			return arr;
		}
		int[] kHeap = new int[k];
		for (int i = 0; i != k; i++) {
			heapInsert(kHeap, arr[i], i);
		}
		for (int i = k; i != arr.length; i++) {
			if (arr[i] < kHeap[0]) {
				kHeap[0] = arr[i];
				heapify(kHeap, 0, k);
			}
		}
		return kHeap;
	}

	public static void heapInsert(int[] arr, int value, int index) {
		arr[index] = value;
		while (index != 0) {
			int parent = (index - 1) / 2;
			if (arr[parent] < arr[index]) {
				swap(arr, parent, index);
				index = parent;
			} else {
				break;
			}
		}
	}

	public static void heapify(int[] arr, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int largest = index;
		while (left < heapSize) {
			if (arr[left] > arr[index]) {
				largest = left;
			}
			if (right < heapSize && arr[right] > arr[largest]) {
				largest = right;
			}
			if (largest != index) {
				swap(arr, largest, index);
			} else {
				break;
			}
			index = largest;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}
	public static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}

O(n)的算法，会用到经典的bfprt算法，该算法于1973年由blum、floyd、pratt、rivest、tarjan联合发明，它解决了这样一个问题，在O(n)时间复杂度内,从无序的数组中找到第k小的数，显而易见的是，如果我们找到了第k小的数，那么想求arr中最小的k个数，就是再遍历一次数组的工作量而已，所以关键的问题就变成了如何理解并实现brprt算法。
bfprt算法是如何找到第k小的数？以下是算法的过程，假设bfprt算法的函数是int select(int[]arr,k)，该函数的功能为在arr中找到第k小的数，然后返回该数。
select(arr,k)的过程如下：
1),将arr中的n个元素划分成n/5组，每组5个元素，如果最后的组不够5个元素，那么最后的元素成为一组(n%5个元素)。
2),对每个数组进行插入排序，只针对每个组最多5个元素之间的组内排序，组与组之间并不排序。排序之后找到每个组的中位数，如果组的元素个数为偶数，这里规定找不到中位数。
3),步骤2中一共会找到n/5个中位数，让这些中位数组成一个新的数组，记为mArr。递归调用select(mArr,mArr.length/2)，意义是找到mArr这个数组中的中位数，即mArr中的第(mArr.length/2)小的数。
4),假设步骤3递归调用select(mArr,mArr.length/2)后，返回的数为x，根据这个x划分整个arr数组(partition过程)，划分的过程为：在arr中，比x小的数都在x的左边，比x大的数都在x的右边，x在中间。假划分完成后，x在arr中的位置记为i。
5)，如果i==k，说明x为整个数组中第k小的数，直接返回。
如果i<k，说明x处在第k小的数的左边，应该在x的右边寻找第k小的数，所以递归调用select函数，在右半区寻找第k-i小的数。
如果i>k，说明x处在第k小的数的右边，应该在x的左边寻找第k小的数，所以递归调用select函数，在左半区寻找第k-i小的数。

bfprt算法为什么能做到O(n)的时间复杂度呢？以下是bfprt时间复杂度的分析：
1，在上述过程，除了步骤3和步骤5要用递归函数外，其他的所有处理过程都可以在O(n)时间内完成。
2，步骤3中有递归函数的调用，且递归处理的数组大小为n/5(即T(n/5))。
3，步骤5也递归调用了select函数，那么递归处理的数组大小最大为多少呢？具体地说，我们关心的是由x划分出的左半区最大有多大和由x划分出去的右半区最大有多大。
数学证明了bfprt算法的时间复杂度是O(n)。
具体请参看如下代码中的getMinKnumsByBFPRT方法。

static int[] getMinKNumsByBFPRT(int[] arr, int k) {

	if (k < 1 || k > arr.length) {
		return arr;
	}
	int minKth = getMinKthByBFPRT(arr, k);
	int[] res = new int[k];
	int index = 0;
	for (int i = 0; i != arr.length; i++) {
		if (arr[i] < minKth) {
			res[index++] = arr[i];
		}
	}
	for (; index != res.length; index++) {
		res[index] = minKth;
	}
	return res;
}

public static int getMinKthByBFPRT(int[] arr, int K) {
	int[] copyArr = copyArray(arr);
	return select(copyArr, 0, copyArr.length - 1, K - 1);
}

public static int[] copyArray(int[] arr) {
	int[] res = new int[arr.length];
	for (int i = 0; i != res.length; i++) {
		res[i] = arr[i];
	}
	return res;
}

public static int select(int[] arr, int begin, int end, int i) {
	if (begin == end) {
		return arr[begin];
	}
	int pivot = medianOfMedians(arr, begin, end);
	int[] pivotRange = partition(arr, begin, end, pivot);
	if (i >= pivotRange[0] && i <= pivotRange[1]) {
		return arr[i];
	} else if (i < pivotRange[0]) {
		return select(arr, begin, pivotRange[0] - 1, i);
	} else {
		return select(arr, pivotRange[1] + 1, end, i);
	}
}

public static int medianOfMedians(int[] arr, int begin, int end) {
	int num = end - begin + 1;
	int offset = num % 5 == 0 ? 0 : 1;
	int[] mArr = new int[num / 5 + offset];
	for (int i = 0; i < mArr.length; i++) {
		int beginI = begin + i * 5;
		int endI = beginI + 4;
		mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
	}
	return select(mArr, 0, mArr.length - 1, mArr.length / 2);
}

public static int[] partition(int[] arr, int begin, int end, int pivotValue) {
	int small = begin - 1;
	int cur = begin;
	int big = end + 1;
	while (cur != big) {
		if (arr[cur] < pivotValue) {
			swap(arr, ++small, cur++);
		} else if (arr[cur] > pivotValue) {
			swap(arr, cur, --big);
		} else {
			cur++;
		}
	}
	int[] range = new int[2];
	range[0] = small + 1;
	range[1] = big - 1;
	return range;
}

public static int getMedian(int[] arr, int begin, int end) {
	insertionSort(arr, begin, end);
	int sum = end + begin;
	int mid = (sum / 2) + (sum % 2);
	return arr[mid];
}

public static void insertionSort(int[] arr, int begin, int end) {
	for (int i = begin + 1; i != end + 1; i++) {
		for (int j = i; j != begin; j--) {
			if (arr[j - 1] > arr[j]) {
				swap(arr, j - 1, j);
			} else {
				break;
			}
		}
	}
}

public static void swap(int[] arr, int index1, int index2) {
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

public static void printArray(int[] arr) {
	for (int i = 0; i != arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

5，需要排序的最短子数组长度
题目：一个无序数组arr，求出需要排序的最短子数组长度。
例如：arr={1,5,3,4,2,6},返回4，因为只有[5,3,4,2]需要排序。
解答：可以做到时间复杂度O(n)，额外空间复杂度O(1)。
初始化变量noMinIndex=-1，从右向左遍历，遍历的过程中记录右侧出现过的数的最小值，记为min。假设当前数为arr[i]，如果arr[i]>min,说明如果要整体有序，min值必然会挪到arr[i]的左边。用noMinIndex记录最左边出现这种情况的位置。如果遍历完成后，noMinIndex依然等于-1，说明从右到左始终不升序，原本数组就有序，直接返回0，即完全不需要排序。
接下来从左往右遍历，遍历的过程中记录左侧出现过的数的最大值，记为max。假设当前数为arr[i]，如果arr[i]<max,说明如果有序，max值必然会挪到arr[i]的右边。用变量noMaxIndex记录最右边出现这种情况的位置。
遍历完成后，arr[noMinIndex…noMaxIndex]就是需要排序的那部分，返回它的长度即可。
具体过程参看下面的getMinLength方法。

   public static int getMinLength(int[] arr) {
	if (arr == null || arr.length < 2) {
		return 0;
	}
	int min = arr[arr.length - 1];
	int noMinIndex = -1;
	for (int i = arr.length - 2; i != -1; i--) {
		if (arr[i] > min) {
			noMinIndex = i;
		} else {
			min = Math.min(min, arr[i]);
		}
	}
	if (noMinIndex == -1) {
		return 0;
	}
	int max = arr[0];
	int noMaxIndex = -1;
	for (int i = 1; i != arr.length; i++) {
		if (arr[i] < max) {
			noMaxIndex = i;
		} else {
			max = Math.max(max, arr[i]);
		}
	}
	return noMaxIndex - noMinIndex + 1;
}

6，在数组中找到出现次数大于n/k的数
题目：给定一个数组，打印其出现次数大于一半的数，如果没有这样的数，打印提示信息。
进阶：给定一个数组arr，再给定一个整数k，打印所有出现次数大于n/k的数，如果没有这样的数，打印提示信息。
要求：原问题要求的时间复杂度为O(n),额外空间复杂度为O(1)，进阶问题要求时间复杂度为O(n*k)，额外空间复杂度为O(k)。
解答：无论是原问题还是进阶问题，都可以用哈希表记录每个数及其出现的次数，但是额外空间复杂度为O(n)，不符合题目要求，所以本书不再详细讲这种方法。本书提供方法的核心思路是，一次在数组中删除k个不同的数，不停地删除，直到剩下数的种类不足k就停止删除，那么，如果一个数在数组中出现的次数大于n/k，则这个数最后一定会被生下来。
原问题，出现次数大于一半的数最多只会有一个，还可能不存在这样的数。具体的过程为，一次在数组中删除两个不的数，不停地删除，直到剩下的数只有一种，如果一个数出现次数大于一半，这个数最后一定会剩下来。如下代码中的printHalfMajor方法。

   public static void printHalfMajor(int[] arr) {
	int cand = 0;
	int times = 0;
	for (int i = 0; i != arr.length; i++) {
		if (times == 0) {
			cand = arr[i];
			times = 1;
		} else if (arr[i] == cand) {
			times++;
		} else {
			times--;
		}
	}
	times = 0;
	for (int i = 0; i != arr.length; i++) {
		if (arr[i] == cand) {
			times++;
		}
	}
	if (times > arr.length / 2) {
		System.out.println(cand);
	} else {
		System.out.println("no such number.");
	}
}

第一个for循环就是一次在数组中删除掉两个不同的数的代码实现。
把cand变量叫候选，times叫作次数，读者先不用纠结这两个变量是什么意义，我们看在第一个for循环中发生了什么。
times=0时，表示当前没有候选，则把当前数arr[i]设为候选，同时把times设置成1.
times!=0时，表示当前有候选，如果当前的数arr[i]与候选一样，同时把times加1，如果当前的数att[i]与候选不一样，就把times减1，减到0则表示又没有候选了。
进阶问题也是类似的思想，一次在数组中删除k个不同的数，不停地删除，直到剩下的数的种类不足k，那么，如果某些数在数组中出现次数大于n/k，则这些数最后一定会剩下来。
具体参看如下的printKMajor方法。

   public static void printKMajor(int[] arr, int K) {
	if (K < 2) {
		System.out.println("the value of K is invalid.");
		return;
	}
	HashMap<Integer, Integer> cands = new HashMap<Integer, Integer>();
	for (int i = 0; i != arr.length; i++) {
		if (cands.containsKey(arr[i])) {
			cands.put(arr[i], cands.get(arr[i]) + 1);
		} else {
			if (cands.size() == K - 1) {
				allCandsMinusOne(cands);
			} else {
				cands.put(arr[i], 1);
			}
		}
	}
	HashMap<Integer, Integer> reals = getReals(arr, cands);
	boolean hasPrint = false;
	for (Entry<Integer, Integer> set : cands.entrySet()) {
		Integer key = set.getKey();
		if (reals.get(key) > arr.length / K) {
			hasPrint = true;
			System.out.print(key + " ");
		}
	}
	System.out.println(hasPrint ? "" : "no such number.");
}

public static void allCandsMinusOne(HashMap<Integer, Integer> map) {
	List<Integer> removeList = new LinkedList<Integer>();
	for (Entry<Integer, Integer> set : map.entrySet()) {
		Integer key = set.getKey();
		Integer value = set.getValue();
		if (value == 1) {
			removeList.add(key);
		}
		map.put(key, value - 1);
	}
	for (Integer removeKey : removeList) {
		map.remove(removeKey);
	}
}

public static HashMap<Integer, Integer> getReals(int[] arr,
		HashMap<Integer, Integer> cands) {
	HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>();
	for (int i = 0; i != arr.length; i++) {
		int curNum = arr[i];
		if (cands.containsKey(curNum)) {
			if (reals.containsKey(curNum)) {
				reals.put(curNum, reals.get(curNum) + 1);
			} else {
				reals.put(curNum, 1);
			}
		}
	}
	return reals;
}

7，在行列都排好序的矩阵中找数
题目：给定一个m*n的整型矩阵matrix和一个整数k，matrix的每一行和每一列都是排好序的。实现函数，判断k是否在matrix中。
例如：
0 1 2 3
2 3 4 7
4 4 4 7
5 7 7 9
如果k为7，返回true；如果k为6，返回false。
要求：时间复杂度为O(n+m)，额外空间复杂度为O(1)。
思路:用以下步骤解决
1),从矩阵最右上角的数开始寻找(row=0,col=m-1)。
2),比较当前数matrix[row][col]与k的关系：
如果与k相等，说明已找到，直接返回true。
如果比k大，因为矩阵每一列都已拍好，所以在当前数所在的列中，处于当前数下方的数都会比k小，则没必要继续在第col列上寻找，令col=col-1，重复步骤2。
如果比k小，因为矩阵每一行都已排好序，所以在当前数所在的行中，处于当前数左方的数都会比k小，则没有必要继续在第row行上寻找，令row=row-1，重复步骤2.
3),如果找到越界都没有发现与k相等的数，则返回false。
或者，也可以用以下步骤。
1),从矩阵最左下角的数开始寻找(row=n-1,col=0)。
2),比较当前数matrix[row][col]与k的关系：
如果比与k相等，说明找到了，返回true。
如果比k大，因为矩阵每一行都已经排好序，所以在当前数所在的行中，当前数右方的数都会比k大，则没有必要继续在第row行上寻找，令row=row-1，重复步骤2.
如果比k小，因为矩阵每一列都已排序，所以在当前数所在的列中，处于数上方的数都会比k小，则没有必要继续在第col列上寻找，令col=col+1，重复步骤。
3),如果越界还没有发现与k相等的数，则返回false。
具体请参看如下代码中的isContains方法：

   public static boolean isContains(int[][] matrix, int K) {
	int row = 0;
	int col = matrix[0].length - 1;
	while (row < matrix.length && col > -1) {
		if (matrix[row][col] == K) {
			return true;
		} else if (matrix[row][col] > K) {
			col--;
		} else {
			row++;
		}
	}
	return false;
}

8， 最长的可整合子数组的长度
题目：给出最长可整合子数组长度定义，一个数组在排序后，每相邻两个数差值的绝对值都为1，则该数组为可整合数组。例如，[5,3,4,6,2],符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组。
给定一个整型数组arr，请返回其中最大可整合子数组的长度。例如，[5,5,3,2,6,3]的最大可整合子数组为[5,3,2,6,4]。
解答：时间复杂度高但简单的解法，对arr中的每一个子数组arri…j，都验证一下是否符合可整合数组的定义，也就是把arr[i..j]排序一下，看是否依次递增且每次递增1。然后在所有符合可整合数组定义的子数组中，记录最大的那个长度，返回即可。需要注意的是，在考察每一个arr[i…j]是否符合数组定义的时候，都得把arr[i…j]单独复制成一个新的数组，然后把这个新的数组排序、验证，而不能直接改变arr中元素的顺序。所以大体过程如下：
1)，依次考查每一个子数组arr[i…j]，一共有n的平方。
2),对每一个子数组arr[i…j]，复制成一个新的数组，记为newArr，把newArr排序，然后验证是否可整合数组的定义，这一步代价为O(nlogn)。
3),步骤3中符合条件的、最大的那个子数组的长度就是结果。
具体参看如下代码中的getLIL1方法，时间复杂度为O(nn) O(nlogn)–>O（nnn * logn）。
代码如下：

public static int getLIL1(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int len = 0;
	for (int i = 0; i < arr.length; i++) {
		for (int j = i; j < arr.length; j++) {
			if (isIntegrated(arr, i, j)) {
				len = Math.max(len, j - i + 1);
			}
		}
	}
	return len;
}

public static boolean isIntegrated(int[] arr, int left, int right) {
	int[] newArr = Arrays.copyOfRange(arr, left, right + 1); // O(N)
	Arrays.sort(newArr); // O(N*logN)
	for (int i = 1; i < newArr.length; i++) {
		if (newArr[i - 1] != newArr[i] - 1) {
			return false;
		}
	}
	return true;
}

这是时间复杂度非常高的方法。
更高效的方法，有没有更高效的判断可整合数组的方法呢？也就是有没有更高效的方法来加速验证呢？判断一个数组是否是可整合数组还可以用以下方法来判断，一个数组中如果没有重复元素，并且如果最大值减去最小值，再加1的结果等于元素个数(max-min+1==元素个数),那么这个数组就是可整合数组。比如[3,2,5,6,4]，max-min+1=6-2+1=元素个数，所以这个数组是可整合数组。
这样，验证一个数组是否是可整合数组的时间复杂度可以从O(nlogn)加速至O(1)，整个过程的时间复杂度就可加速到O(n*n)。具体参看如下代码中的getLIL2方法。

   public static int getLIL2(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int len = 0;
	int max = 0;
	int min = 0;
	HashSet<Integer> set = new HashSet<Integer>(); 
	for (int i = 0; i < arr.length; i++) {
		max = Integer.MIN_VALUE;
		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]);
			if (max - min == j - i) { 
				len = Math.max(len, j - i + 1);
			}
		}
		set.clear();
	}
	return len;
}