# Shortest unsorted continuous subarray

Posted by chunyang on April 4, 2019

### 题目

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

### 解法

#### 思路

• 有序数组
• 无序数组
• 有序数组

[1, 2, 3, 5]

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

maxs: [2, 6, 6, 8, 10, 10, 15]

• 如果位于这个位置，则说明乱序的元素都比左侧有序数组大
• 如果位于这个位置左侧，则说明乱序元素有比左侧有序数组元素还大的点

#### 代码

class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
vector<int> maxs;
int length = nums.size();
maxs.reserve(length);
int current_max = nums[0];
for (int& num : nums) {
if (num > current_max) {
current_max = num;
}
maxs.push_back(current_max);
}
int i = length - 1;
while (i >= 0) {
if (nums[i] == maxs[i]) {
--i;
} else {
break;
}
}
int end = i;
/* corner case: already sorted */
if (i < 0) return 0;

i = 0;
while (i < length) {
if (maxs[i] == nums[i]) {
++i;
} else {
break;
}
}
int start = i;
int min_in_unsorted = nums[i];
while (i <= end) {
if (nums[i] < min_in_unsorted) {
min_in_unsorted = nums[i];
}
++i;
}

start = distance(
nums.begin(),
upper_bound(nums.begin(), nums.begin()+start, min_in_unsorted));

/* cout << "end = " << end << " start = " << start;
cout << " min_in_unsorted = " << min_in_unsorted << endl; */

return end - start + 1;
}
};


• upper_bound
• distance