05 August 2008
给一个整数数组，找出最小的子数组，把该子数组sort后，这个数组也就排序好了，返回该子数组的长度
use the variables beg and end to keep track of minimum subarray nums[beg…end] which must be sorted for the entire array nums to be sorted. If end < beg < 0 at the end of the for loop, then the array is already fully sorted.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length, beg = -1, end = -2, min = nums[n-1], max = nums[0];
for (int i = 1; i < n; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[n - 1 - i]);
if (nums[i] < max) end = i;
if (nums[n - 1 - i] > min) beg = n - 1 - i;
}
return end - beg + 1;
}
}