# C#LeetCode刷题之#581-最短无序连续子数组（ Shortest Unsorted Continuous Subarray）

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.

Input: [2, 6, 4, 8, 10, 9, 15]

Output: 5

Explanation: 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 <=.

```public class Program {

public static void Main(string[] args) {
int[] nums = null;

nums = new int[] { 2, 6, 4, 8, 10, 9, 15 };
var res = FindUnsortedSubarray(nums);
Console.WriteLine(res);

res = FindUnsortedSubarray2(nums);
Console.WriteLine(res);

res = FindUnsortedSubarray3(nums);
Console.WriteLine(res);

}

private static int FindUnsortedSubarray(int[] nums) {
var newNums = new int[nums.Length];
Array.Copy(nums, newNums, nums.Length);
Array.Sort(newNums);
//先排序并赋初始值
int begin = 0, end = nums.Length - 1;
//如果之前的数据就在正确的位置上，就移动指针位置
while(nums[begin] == newNums[begin] && begin < end)
begin++;
while(nums[end] == newNums[end] && begin < end)
end--;
//相等时，代表之前就是有序的
if(begin == end)
return 0;
else
return end - begin + 1;
}

private static int FindUnsortedSubarray2(int[] nums) {
//FindUnsortedSubarray的优化写法
var newNums = new int[nums.Length];
Array.Copy(nums, newNums, nums.Length);
Array.Sort(newNums);
int begin = -1, end = -2;
for(int i = 0; i < nums.Length; i++) {
if(nums[i] != newNums[i]) {
if(begin == -1)
begin = i;
end = i;
}
}
return end - begin + 1;
}

private static int FindUnsortedSubarray3(int[] nums) {
//此解法参考英文官方LeetCode上的讨论
//CSDN和cnblog上关于此解法讨论基本上都是错误的
//很多博主参考此解法给出了正确的实现，但是解释的均不对
//至少我本人没有发现任何一篇的解释是对的，经不起推敲，一个反例即可
//其实这个解法和FindUnsortedSubarray解法的基本思路类似
//从左到右（或从右到左）找最小值（或最大值），看这个最小值（或最大值）是否在其应该存在的地方
//例如第1次，找出数组中第1小的值，看其是不是在索引为0的地方
//如果不是，查找结束，start为0
//如果是，找出数组中第2小的值，看其是不是在索引为1的地方
//以此类推，从右向左找最大值的方式类似
//以上分析才是这个解法的精髓所在，思路同FindUnsortedSubarray
//但解法巧妙至极，是一种高度优化的写法
int n = nums.Length;
//赋初始开始和结束值
int start = -1;
int end = -2;
//结束值赋为-2是考虑在数组本身就是有序时
//最后一句的return也可以给出正确值
//因为 end = i 没有被执行
int min = nums[n - 1];
int max = nums[0];
//
for(int i = 0, pos = 0; i < n; i++) {
pos = n - 1 - i;
//找出局部最大、最小值
max = Math.Max(max, nums[i]);
min = Math.Min(min, nums[pos]);
//如果当前值小于局部最大值，重置end
if(nums[i] < max)
end = i;
//如果当前值大于局部最小值，重置start
if(nums[pos] > min)
start = pos;
}
//返回开始和结束的索引差
//假如是1、2，2 - 1 + 1 = 2，因为1，2是2个值
return end - start + 1;
}

}```

```5
5
5```

(1)