581. Shortest Unsorted Continuous Subarray
难度: Easy
刷题内容
原题连接 * https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
内容描述 ``` 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。 ```
解题方案
思路 1
1. 拷贝数组，排序
2. 计算两个数组不同的起始位置和末端位置
3. 计算差值
int findUnsortedSubarray(vector<int>& nums) {
vector<int> tmp(nums.begin(), nums.end());
sort(tmp.begin(), tmp.end());
int start=-1, end=-1;
for(int i=0;i<nums.size();i++){
if(tmp[i]!=nums[i]){
start = i;
break;
}
}
for(int i=nums.size()-1;i>=0;i--){
if(tmp[i]!=nums[i]){
end = i;
break;
}
}
if(start==-1&&end==-1)
return 0;
return end-start+1;
}
