题目描述
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。
思路：我们先定义一个和nums大小相同的int类型数组temp，将nums中的元素有序插入temp中。这个时候temp中的元素相当于是nums中的元素排好序的结果。我们定义两个变量left和right从两个数组两边寻找第一个不同的元素，最后用找得到结果相减加1就得到最短无序连续子数组。
int findUnsortedSubarray(int* nums, int numsSize)
{
int temp[numsSize];
int len = 0, left = 0, right = numsSize - 1;
for (int i = 0; i < numsSize; ++i)//将nums中的元素有序插入temp中
{
int j = 0;
for (j = len - 1; j >= 0 && temp[j] > nums[i]; --j)
{
temp[j + 1] = temp[j];
}
temp[j + 1] = nums[i];
++len;
}
while (left <= right && nums[left] == temp[left])//找到左边第一个不同的元素
{
++left;
}
while (left < right && nums[right] == temp[right])//找到右边第一个不同的元素
{
--right;
}
return right - left + 1;
}