题目
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
思路
方法一：双指针 + 排序
最终目的是让整个数组有序，那么可以先将数组拷贝一份进行排序，然后使用两个指针 i和 j分别找到左右两端第一个不同的地方，那么 [i,j]这一区间即是答案
java代码如下：
class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;int[] arr = nums.clone();//java中的clone对于一维数组是深拷贝，重新分配空间，并将元素复制过去，对clone后的数组进行修改不会影响源数组。但是对二维数组是浅拷贝，复制的是引用，实际上指向的是同一个地址，对拷贝的二维数组修改或者排序都会影响原二维数组Arrays.sort(arr);int i = 0, j = n - 1;while (i <= j && nums[i] == arr[i]) i++;while (i <= j && nums[j] == arr[j]) j--;return j - i + 1;}
}
方法二：双指针 + 线性扫描（一次遍历）
将整个数组分成三段处理，一次遍历
正常排序(1 2 3 4 5): 左边所有元素的最大值(2) <= 每个元素(例如3) <= 右边所有元素的最小值(4)
求解: 2 6 8 10 4 9 15
其中:
从左到右 9是最后一个小于 (左边所有元素最大值)的
从右到左 6是最后一个大于 (右边所有元素最小值)的
故解为求:
- 从左到右遍历, 记录当前遍历数的最大值, 最后一个小于最大值的即 需要倒置数组的右边边界索引
- 从右到左遍历, 记录当前遍历数的最小值, 最后一个大于最小值的即 需要倒置数组的左边边界索引
java代码如下（算法有点晦涩难懂，建议跟着例子在纸上走一遍）：
class Solution{public int findUnsortedSubarray(int[] nums) {int length = nums.length;int leftDiff = -1;int rightDiff = -1;//最大值是顺序遍历使用的(求需排序数组的右边边界索引rightDiff), 也可以取Integer.MIN_VALUEint max = nums[0];//最小值是倒序遍历使用的(求需排序数组的左边边界索引leftDiff), 也可以取Integer.MAX_VALUEint min = nums[length - 1];for (int i = 0; i < length; i++) {//顺序执行, 判断 当前值是否小于 已遍历的最大值, 是的话属于需排序的数组元素, 替换rightDiff; 否就更新最大值if (nums[i] < max){rightDiff = i;} else {max = nums[i];}//倒序执行, 判断 当前值是否大于 已遍历的最小值, 是的话属于需排序的数组元素, 替换leftDiff; 否就更新最小值int index = length - 1 - i;if (nums[index] > min){leftDiff = index;} else {min = nums[index];}}return leftDiff != -1 ? rightDiff - leftDiff + 1 : 0;}
}
