1. 题目描述
首先我们来了解一下这个问题的具体描述。
给定一个整数数组，你需要找到一个连续子数组，使得这个子数组中的元素进行升序排序后，整个数组就变成升序排序。你需要找到这个子数组并返回其长度。如果整个数组就是有序的，你需要返回 0。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你需要排序的子数组是 [6, 4, 8, 10, 9]。
示例 2:
输入: [1, 2, 3, 4]
输出: 0
解释: 整个数组已经有序。
注意:
输入的数组长度范围在 [1, 10,000] 之间。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
2. 题目解析
2.1 思路
首先我们来做一个简单的分析。我们要找到一个排序后使得整个数组变成有序数组的子数组。那么它的左边和右边的那些元素也都不是有序的。
2.2 解法
不难发现，找到那个最小的没有放在正确位置的元素和最大的没有放在正确位置的元素，就可以得到这个最短的无序子数组。
因此，我们可以从左到右找到那个最大的没有放在正确位置的元素，再从右到左找到那个最小的没有放在正确位置的元素。它们之间就是最短无序子数组了。
2.3 时间复杂度
时间复杂度为 O(n)，其中 n 是数组的长度。
2.4 空间复杂度
空间复杂度为 O(1)
3. 代码实现
/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function(nums) {
var n = nums.length;
if (n < 2) {
return 0;
}
var start = 0;
var end = 0;
var i, j;
var max = nums[0];
var min = nums[n - 1];
for (i = 1; i < n; i++) {
if (nums[i] < max) {
end = i;
} else {
max = nums[i];
}
}
for (j = n - 2; j >= 0; j--) {
if (nums[j] > min) {
start = j;
} else {
min = nums[j];
}
}
if (end > start) {
return end - start + 1;
} else {
return 0;
}
};