Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]Output: 5Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
- Then length of the input array is in range [1, 10,000].
- The input array may contain duplicates, so ascending order here means <=.
解决方案：
①自己编写，用时59ms。思路：将数组复制到一个新的数组，对新的数组进行排序，分别从头部和尾部扫描数组，若有不同则立即停止，记录下出现不同的位置，两者的差值加1的到子数组的长度。注意数组的边界值。实现代码如下：
public class Solution {
public int findUnsortedSubarray(int[] nums) { int len = 0; int start = 0; //初始若为0，则需要注意两数组相同时长度为0 int end = 0; int[] arr = nums.clone(); Arrays.sort(arr); for(int i = 0; i <= nums.length-1 ; i ++){ if(nums[i] != arr[i]){ start = i; break; } } for(int i = nums.length - 1; i >= 0 ; i --){ if(nums[i] != arr[i]){ end = i; break; } } if(end != 0){ len = end - start + 1; return len; } return 0; } }②之后，在discuss部分找到了同一个思路但是更为简洁的方法,38ms：
public class Solution {
public int findUnsortedSubarray(int[] nums) { int[] arr = nums.clone(); Arrays.sort(arr); int start = arr.length;//注意起始位置！！ int end = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] != nums[i]) { start = Math.min(start, i); end = Math.max(end, i); } } return (end - start >= 0 ? end - start + 1 : 0); } }以上两种方法的时间复杂度为：O(nlogn)，为数组排序的时间。空间复杂度为 O(n)，因为对数组进行了复制。
③第三种方法是使用栈（95ms），只要数值大于前一个将下标从0依次入栈，因为此时都是升序，当遇到第一个降序时，就是我们要找的start,此时只要pop()出该下标值即可，因为是从头到尾遍历，我们只要找到下标最小的一个即可。同理可以找到end。
public class Solution {
public int findUnsortedSubarray(int[] nums) { Stack < Integer > stack = new Stack < Integer > (); int start = nums.length; int end = 0; for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) start = Math.min(start, stack.pop()); stack.push(i); } stack.clear(); for (int i = nums.length - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) end = Math.max(end, stack.pop()); stack.push(i); } return end - start > 0 ? end - start + 1 : 0; } }时间复杂度：O(n)，for循环 空间复杂度：O(n)，最多入栈n个。
④ 采用四个指针，start,end,max,min，初始时，start=nums.length，end=-1，max=nums[0]，min=nums[1]然后将end和max指针从头到尾扫描，使max指向最大值，而end指向无序数列最后一个值。同理，从尾到头扫描得到min和start的值。耗时21ms.
public class Solution {
public int findUnsortedSubarray(int[] nums) { if(nums.length < 2) return 0; int end = -1; int start = nums.length; int max = nums[0]; int min = nums[nums.length-1]; for (int i = 0;i < nums.length ;i ++ ) { if(nums[i] >= max){//按照顺序排序的 max = nums[i]; }else{//不按照顺序排序的 end = i; } } if(end == -1) return 0;//不能忘记判断，否则顺序都正确时会出错 for (int i = nums.length - 1;i >= 0 ;i -- ) { if(nums[i] <= min){//按照顺序排序的 min = nums[i]; }else{//不按照顺序排序的 start = i; } } //end和start指向的并集，即为无序列 return end - start + 1; } }